I want to count all the unique characters in a given string. So for string "abcaabbd" the length should be 4.

My solution:

    public static void unique(String s){
        int max = 0;
        HashSet<Character> set = new HashSet<Character>();
        for(int i = 0; i < s.length(); i  ){
            set.add(s.charAt(i));
        }
        max = set.size();
        System.out.println(max);
    }

which works fine but I was thinking if there is any way to reduct the time complexity of the operation.

CodePudding user response：

This task couldn't be solved in asymptotic complexity that less than O(n) because you have to iterate over all elements of your string (with length n) at least one time to count unique chars in this string (it's pretty obvious I guess). Your solution has exactly O(n) asymptotic complexity: you iterate over the chars of the string, on each step of your loop you put some value in HashSet that takes O(1), then you get set.size that takes O(1) time too. The overall complexity is O(n) then and that's the minimum complexity that you can achieve.

But actually HashSet requires more memory than regular array. And if any string that you are going to pass to your function is guaranteed to consist of some limited set of chars (for example any string you pass to your function only consists of ASCII symbols) you could create an array with length of this limited set (for ASCII symbols it would be 256). Then on each step of iterating over chars of your string you could increment element of created array with index equal to ASCII code of that char (this approach is similar to counting sort). And then you could iterate over your array and just count non-zero elements. That would be number of unique symbols in your string. It would reduce memory utilization of you function and would have the same asymptotic complexity(O(n)). But nevertheless I don't recommend this approach as it's not a production solution.

CodePudding user response：

You can use a boolean array to keep track of the characters you have seen. The array will have 256 elements, one for each possible character. You can then iterate through the string and set the corresponding element in the array to true. At the end, you can count the number of true elements in the array. This will be O(n) time and O(1) space. The code would look something like this:

public static int unique(String s) {
    boolean[] seen = new boolean[256];
    for (int i = 0; i < s.length(); i  ) {
        seen[s.charAt(i)] = true;
    }
    int count = 0;
    for (int i = 0; i < seen.length; i  ) {
        if (seen[i]) {
            count  ;
        }
    }
    return count;
}