Number of substrings with unique letters

Question

I have a string, now want to count the minimum number of substrings such that the letters in the substring should occur only once.

Example:

Input : cycle
Output : 2

explanation:

Possible substrings are : ('cy', 'cle') or ('c', 'ycle')

Example:

Input : aaaa
Output : 4

explanation:

Possible substrings are : ('a', 'a', 'a', 'a')

I am able to get all possible substrings but I am not able to understand how to achieve the solution for this task:

static int distinctSubString(String S) {
    int count = 0;
    int n = S.length();
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j <= n; j++) {
            String s = S.substring(i, j);
            System.out.println(s);
        }
    }
    return count;
}

Answer 1

You should note that this can be done greedily. Whenever you meet a character it can either be added to the previous partition or can start a new one. If both are possible, then you can always add to the previous partition and not change anything else, so the answer would not get worse from it. Therefore, the solution is to run across characters and whenever you and add one to the partition when you can do it. This solution is asymptotically optimal. Note that if your characters fall into a specific range using an array instead of HashSet can significantly boost performance.

static int distinctSubString(String S) {
    int count = (S.isEmpty()) ? 0 : 1;
    S = S.toLowerCase();
    HashSet<Character> letters = new HashSet<Character>();
    for (int i = 0; i < S.length(); i++) {
        if (letters.contains(S.charAt(i))) {
            letters.clear();
            count++;
        }
        letters.add(S.charAt(i));
    }
    return count;
}