First Unique Character in a String

Given a string s, find the first non-repeating character in it and return its index. If it does not exist, return -1.

 

Example 1:

Input: s = "leetcode"
Output: 0

Example 2:

Input: s = "loveleetcode"
Output: 2

Example 3:

Input: s = "aabb"
Output: -1

 

Constraints:

• 1 <= s.length <= 10^5
• s consists of only lowercase English letters.

 

첫번째로 발견된 unique한 char이 무엇인지 반환하는 문제이다. 가장 단순하게 $N^2$으로 푸는 방법이 있을것이고, map을 이용해서 각 char의 갯수를 저장해서 푸는방법도 있을것이다. 조금 재미있게, 그리고 아주 작은 공간을 사용하기 위해서, 힌트에서 소문자 알파벳만 쓰인다는 조건이 있었고, 스트링의 길이도 10000이 최대이기 때문에, 2N, 즉 O(N)으로 푸는 솔루션으로 해법을 찾았다.

 

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

처음으로 스트링을 돌면서 각 알파벳이 몇개인지 센다. 이때 각 char에서 'a'를 빼준값을 index로 사용한다. 이후, 다시한번 스트링을 돌면서 각 캐릭터에 해당하는 값이 count array에서 1인지 확인하면 된다.

 

String을 2번 돌았기 때문에 O(N)의 time complexity가 예상되고, 26사이즈의 array를 사용했기 때문에 O(1)의 space complexity가 사용되었다. 이 솔루션으로 했을때 89.53% 빠른 속도를 보였고, space도 꽤 좋았다.

 

혹시나 하는 궁금증으로 map을 사용해보았는데 위 해법보다 훨씬 느렸다.

import java.util.Map;

class Solution {
    public int firstUniqChar(String s) {
        Map<Character, Integer> map = new HashMap<>(); 
        for(int i = 0; i < s.length(); i++){
            int curr = map.getOrDefault(s.charAt(i), 0);
            map.put(s.charAt(i), curr + 1);
        }
        
        for(int i = 0; i < s.length(); i++){
            if(map.get(s.charAt(i)) == 1){
                return i;
            }
        }
        return -1;
    }
}

 

 

pokemon에서 unique한 첫번째 char의 index는? 0

 

https://leetcode.com/problems/first-unique-character-in-a-string/

First Unique Character in a String - LeetCode