Java one-pass and two-pass


  • 2
    Some company has follow-up questions: how to do one-pass
    two pass:
    public class Solution {
        public int firstUniqChar(String s) {
           int[] frequency = new int[26];
           for (char c : s.toCharArray()) {
               frequency[c - 'a']++;
           }
           for (int i = 0; i < s.length(); i++) {
               char c = s.charAt(i);
               if (frequency[c - 'a'] == 1) {
                   return i;
               }
           }
           return -1;
        }
    }
    
    one-pass
    
    public class Solution {
        public int firstUniqChar(String s) {
            int[] alphabet = new int[26];
            Arrays.fill(alphabet, -1);
            for (int i = 0; i < s.length(); i++) {
                char c = s.charAt(i);
                if (alphabet[c - 'a'] == -1) { // first time letter
                    alphabet[c - 'a'] = i;
                } else {
                    alphabet[c - 'a'] = -2; //  mark as repeated letter
                }
            }
            int first = s.length();
            for (int index : alphabet) {
                if (index >= 0 && index < first) {
                    first = index;
                }
            }
            return first == s.length() ? -1 : first;
        }
    }

Log in to reply
 

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