Java 7 lines solution 29ms


  • 95

    Hey guys. My solution is pretty straightforward. It takes O(n) and goes through the string twice:

    1. Get the frequency of each character.
    2. Get the first character that has a frequency of one.

    Actually the code below passes all the cases. However, according to @xietao0221, we could change the size of the frequency array to 256 to store other kinds of characters. Thanks for all the other comments and suggestions. Fight on!

    public class Solution {
        public int firstUniqChar(String s) {
            int freq [] = new int[26];
            for(int i = 0; i < s.length(); i ++)
                freq [s.charAt(i) - 'a'] ++;
            for(int i = 0; i < s.length(); i ++)
                if(freq [s.charAt(i) - 'a'] == 1)
                    return i;
            return -1;
        }
    }
    

  • 0
    H

    Beautiful O(n) solution


  • 11

    Nice Solution, one thing need to notice that if the string contains any characters which are represented by ASCII, we'd better use int[256]. Hope it helps!
    Fight on!


  • 6
    G

    Good O(n) solution, but it still can be improved, since you read through the whole array twice. Take an example of DNA sequence: there could be millions of letters long with just 4 alphabet letter. What happened if the non-repeated letter is at the end of DNA sequence? This would dramatically increase your running time since we need to scan it again.


  • 0
    D

    there is one question,is there any chance that "Custom Testcase" includes any numbers or other non-letter char?In that situation how to solve this problem?


  • 3

    @dongshuai please use int[256] as the freq array, because 256 is the size of ASCII.


  • 0
    D

    @xietao0221 yes,thanks


  • 0
    D

    @gh603 This is a good point, can you suggest improvement in above solution to handle such cases.


  • 0
    H

    good sulotion, the time complex is O(n)


  • 4
    S

    if you could record the first appearance of every char, you don't have to check the string twice.
    table[256][2] [0] for first appearance, [1] for frequency. the second time you only have to check 256 numbers.


  • 0
    C

    @xietao0221 as for int[256], if string contains % this kind of letter. will the difference of '%' - 'a' lie in the range of 0 - 256?
    thanks


  • 2

    @crazystonesss said in Java 7 lines solution 29ms:

    %

    if you use int[256], you just use charSet[c] rather than charSet[c - 'a']. The reason why you use [c - 'a'] is when you know the targets are all lower case letters whose range is from 'a' to 'z'. Or you use [c - 'A'] if the targets are all upper case letters.


  • 3
    U

    runtime 15ms,beats 98.2% same concept:

       public int firstUniqChar(String s) {
           int[] alp =new int[26];
            char[] arr =s.toCharArray();
        
        for(char c : arr ){
            alp[c-'a']++;
        }
        
        for(int i=0;i<arr.length;i++){
            if (alp[arr[i]-'a']==1) return i;
        }
    
        return -1;
    }

  • 0

    Cool O(n) solution, thanks.


  • 1

    a question like this, at least should try to do in one parse


  • 1

    C# - 2 pass

        public int FirstUniqChar(string s) 
        {
            int[] map = new int[26];
            foreach (char c in s) map[c-'a']++;
            for (int i = 0; i < s.Length; i++) if (map[s[i]-'a'] == 1) return i;
            return -1;
        }
    

  • 0
      public int firstUniqChar(String s) {
        char[] map = new char[26];
        char[] sc = s.toCharArray();
        for(char c: sc){
          map[c - 'a']++;
        }
        for(int i=0;i < sc.length;i++){
          if(map[sc[i] - 'a'] == 1) return i;
        }
        
        return -1;        
      }

  • 0
    Z
    This post is deleted!

  • 0
    Z

    For large Strings, a 26-length array may help for the 2nd for loop, so that it will avoid to loop to the end of the String.

            int[] cnt = new int[26];
            int[] pos = new int[26];
            for(int i = 0; i < s.length(); ++i){
                if(cnt[s.charAt(i)-'a'] > 0) cnt[s.charAt(i)-'a']++;
                else{
                    pos[s.charAt(i)-'a'] = i;
                    cnt[s.charAt(i)-'a']++;
                }
            }
            int min=s.length();
            for(int i = 0; i < cnt.length; ++i){
                if(cnt[i] == 1) min = Math.min(min, pos[i]);
            }
            return min==s.length()?-1:min;
    

  • 0
    F

    The same with my code! I am shocked!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.