【LeetCodeに挑戦】387.First Unique Character in a String

現在ITエンジニアとして働いていますが、コーディング・アルゴリズム力をもっと鍛えたいと思い、LeetCodeで学んだ内容をメモ的にアウトプットしています。
今回解いてみた問題は「387.First Unique Character in a String」です。

問題

文字列sが与えられており、最初のユニーク文字のインデックス番号を求める。存在しない場合は-1を返す。（難易度はEasy）

例

Input: s = "leetcode"

Output: 0

Explanation:

The character 'l' at index 0 is the first character that does not occur at any other index.

Input: s = "loveleetcode"

Output: 2

Example 3:

Input: s = "aabb"

Output: -1

制約

• 1 <= s.length <= 10^5

• s consists of only lowercase English letters.

私のダメな解法

class Solution:
    def firstUniqChar(self, s: str) -> int:
        for i in range(len(s)):
            this_word = s[i]
            rest_words = s[:i] + s[i+1:]
            if this_word not in rest_words:
                return i
        
        return -1

このコードの課題

■時間計算量が高い（O(n²)）
スライス操作 (s[:i] + s[i+1:]): 各ループで文字列をスライスし、結合する操作は O(n) の時間がかかる。
not in 操作 (this_word not in rest_words): O(n) の時間がかかる。
結果的に各ループで O(n) の操作が行われ、それが n 回 繰り返されるため、全体の時間計算量は O(n²) となる。

■スペースの非効率な使用
文字列の長さ n に対して、各ループで O(n) のメモリが必要となり、全体で O(n²) のメモリを消費する。

■文字の存在確認が非効率（not in 操作）
文字列内での not in 操作は、内部的には線形探索を行い、一つずつ文字を比較する。最悪の場合、文字列全体をチェックする必要がある。
各ループでの存在確認が O(n) の時間を要する。

理想的な解法

class Solution:
    def firstUniqChar(self, s: str) -> int:
        """
        :type s: str
        :rtype: int
        """
        # build hash map: character and how often it appears
        count = collections.Counter(s)
        
        # find the index
        for idx, ch in enumerate(s):
            if count[ch] == 1:
                return idx     
        return -1

学んだこと：アルゴリズム

• collections.Counterを使用して、各文字が文字列 s に何回出現するかをカウントできる。

• スライス操作 (s[:i] + s[i+1:]) や結合操作（+）は、文字列の一部を新しくコピーして結合するため、文字列の長さに比例して時間がかかる。

• 文字セットが固定（例えば、English Alphabet 26 letters）である場合、空間計算量は入力の大きさ n に依存せず、O(1)と判断できる。