Find Duplicate characters in a string

The problem, simply

You get a string. Find every character that appears more than once, and say how many times it appears. List them in the order they first show up in the string.

Capital and small letters are different characters unless the interviewer says otherwise.

A story to remember it

Picture it

Examples

Way 1: the simple way

For each letter, walk the rest of the string and count its copies. Mark every copy you find so you do not count the same letter again later.

1. For each spot i that is not marked, count how many later spots j hold the same letter, and mark them.
2. If the count is more than 1, write down the letter and its count.

import java.util.*;

class Solution {
    public Map<Character, Integer> duplicates(String s) {
        Map<Character, Integer> out = new LinkedHashMap<>();
        boolean[] counted = new boolean[s.length()];
        for (int i = 0; i < s.length(); i++) {
            if (counted[i]) continue;                 // this letter is already done
            int count = 1;
            for (int j = i + 1; j < s.length(); j++) {
                if (s.charAt(j) == s.charAt(i)) {
                    count++;
                    counted[j] = true;                // do not count this copy again
                }
            }
            if (count > 1) out.put(s.charAt(i), count);
        }
        return out;
    }
}

How long it takes: for each letter we may walk the whole rest of the string, O(n^2). Extra room: the marks, O(n).

Way 2: the clever way

Keep a tally sheet. In code it is an array of 256 counters, one per character, or a hash map when the characters can be anything.

1. Read the string once. For each character c, add 1 to count[c].
2. Read the string a second time. When you meet a character whose count is more than 1, write it down with its count, then set its count to 0 so you do not write it again.

import java.util.*;

class Solution {
    public Map<Character, Integer> duplicates(String s) {
        int[] count = new int[256];                   // one counter per character
        for (int i = 0; i < s.length(); i++) count[s.charAt(i)]++;

        Map<Character, Integer> out = new LinkedHashMap<>();
        for (int i = 0; i < s.length(); i++) {       // second walk keeps first seen order
            char c = s.charAt(i);
            if (count[c] > 1) {
                out.put(c, count[c]);
                count[c] = 0;                         // report each letter once
            }
        }
        return out;
    }
}

How long it takes: two walks over the string, O(n). Extra room: one counter per possible character, O(k), where k is the alphabet size. For 256 characters that is a fixed size.

Watch out for

• A HashMap does not keep insertion order. Use LinkedHashMap, or walk the string again as above, if order matters.
• int[256] crashes on any character above 255, like the euro sign or an emoji. Use int[65536] or a HashMap<Character, Integer> for any text.
• Spaces count as characters too. a b c has two spaces. Ask whether to skip them.

What interviewers ask next

• Can you do it with no extra counters? Sort the characters first, then equal letters sit next to each other and you count runs. That is O(n log n) time, and it loses the original order.
• Only lowercase a to z and no extra room at all? Use the 26 bits of one int as "seen once" flags and another int as "seen twice" flags. This finds which letters repeat, but not how many times.
• First character that does not repeat? Same tally sheet, then walk the string and return the first letter with count 1.
• Are two strings anagrams? Add 1 for each letter of the first, take 1 for each letter of the second, then check that every counter is 0.

Remember this

Grown-up words: the tally sheet is a frequency table, stored as a count array or a hash map, reading it in first seen order uses a LinkedHashMap or a second pass, and k is the alphabet size.