🖋

LeetCode 387. First Unique Character in a String (Python3)

に公開
Python
LeetCode
tech

はじめに

LeetCode 「387. First Unique Character in a String」の問題を Python3 で解きました。

問題

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

問題文

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

和訳
文字列sが与えられた場合、その文字列中の最初の非重複文字を探し、そのインデックスを返します。存在しない場合は-1を返します。

例

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

Input: s = "aabb"

Output: -1

制約

  • 1 <= s.length <= 105
  • s consists of only lowercase English letters.

解答1

最初の非重複文字のインデックスを返す問題です。

非重複か判定するには、最終的にその文字が何回出てきたかをカウントする必要があります。
そしてカウントが1となる最初の要素のインデックスを探索します。

collections.Counterを使用して簡潔に書けます。

コード

class Solution:
    def firstUniqChar(self, s: str) -> int:
        counts = collections.Counter(s)
        for i, ch in enumerate(s):
            if counts[ch] == 1:
                return i
        return -1

計算量

  • 時間的計算量：O(n)
    • Counterの構築にO(n)
    • もう一度文字を走査するのにO(n)
    • 合計O(2n) = O(n)
  • 空間的計算量：O(1)
    • 文字は英小文字だけで最大26なので定数扱い
GitHubで編集を提案

Discussion