Find the first non repeating character in a string

Question

I m writing a method to find the first non repeating character in a string. I saw this method in a previous stackoverflow question

public static char findFirstNonRepChar(String input){
 char currentChar = '\0';
 int len = input.length();
 for(int i=0;i<len;i++){
    currentChar = input.charAt(i);
    if((i!=0) && (currentChar!=input.charAt(i-1)) && (i==input.lastIndexOf(currentChar))){
        return currentChar;
    }
 }
 return currentChar;
}

I came up with a solution using a hashtable where I have two for loops (not nested) where I interate through the string in one loop writing down each occurance of a letter (for example in apple, a would have 1, p would have 2, etc.) then in the second loop I interate through the hashtable to see which one has a count of 1 first. What is the benefit to the above method over what I came up with? I am new to Java does having two loops (not nested) hinder time complexity. Both these algorithms should have O(n) right? Is there another faster, less space complexity algorithm for this question than these two solutions?

Answer 1

public class FirstNonRepeatCharFromString {

    public static void main(String[] args) {

        String s = "java";
        for(Character ch:s.toCharArray()) {
            if(s.indexOf(ch) == s.lastIndexOf(ch)) {
                System.out.println("First non repeat character = " + ch);
                break;
            }
        }
    }
}

Answer 2

As you asked if your code is from O(n) or not, I think it's not, because in the for loop, you are calling lastIndexOf and it's worst case is O(n). So it is from O(n^2).

About your second question: having two loops which are not nested, also makes it from O(n).

If assuming non unicode characters in your input String, and Uppercase or Lowercase characters are assumed to be different, the following would do it with o(n) and supports all ASCII codes from 0 to 255:

public static Character getFirstNotRepeatedChar(String input) {

    byte[] flags = new byte[256]; //all is initialized by 0 

    for (int i = 0; i < input.length(); i++) { // O(n)
        flags[(int)input.charAt(i)]++ ;
    }

    for (int i = 0; i < input.length(); i++) { // O(n)
        if(flags[(int)input.charAt(i)] > 0)
            return input.charAt(i);
    }

    return null;
}

Thanks to Konstantinos Chalkias hint about the overflow, if your input string has more than 127 occurrence of a certain character, you can change the type of flags array from byte[] to int[] or long[] to prevent the overflow of byte type.

Hope it would be helpful.