[LeetCode] 387. First Unique Character in a String

Problem

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.

Solution

Approach

1. 자료구조 Map을 선언하고, 문자열의 각 문자를 Key로, 해당 문자가 등장하는 횟수를 Value로 Map을 구성한다.

2. 문자열의 각 문자를 Key로 Value를 참조하여 1이 등장하면 해당 문자의 인덱스를 반환한다.

   Code

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

   Time Complexity

   • 문자열 s의 길이를 n이라 가정할 때, 코드의 수행 시간을 지배하는 것은 for반복문의 n번 계산 횟수이다. 따라서 본 솔루션은 O(n)의 시간 복잡도를 가진다.