Question

387. 字符串中的第一个唯一字符

English Version

题目描述

给定一个字符串 s ，找到 _它的第一个不重复的字符，并返回它的索引_ 。如果不存在，则返回 -1 。

 

示例 1：

输入: s = "leetcode"
输出: 0

示例 2:

输入: s = "loveleetcode"
输出: 2

示例 3:

输入: s = "aabb"
输出: -1

 

提示:

• 1 <= s.length <= 105
• s 只包含小写字母

解法

方法一：数组或哈希表

我们可以用数组或哈希表 $cnt$ 记录字符串 $s$ 中每个字符出现的次数。

然后我们再遍历字符串 $s$，当遍历到某个字符 $c$ 时，如果 $cnt[c]=1$，则说明 $c$ 是第一个不重复的字符，返回它的索引即可。

如果遍历完字符串 $s$ 仍然没有找到不重复的字符，返回 $-1$。

时间复杂度 $O(n)$，空间复杂度 $O(\Sigma)$，其中 $\Sigma$ 是字符集的大小。

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

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

class Solution {
public:
  int firstUniqChar(string s) {
    int cnt[26]{};
    for (char& c : s) {
      ++cnt[c - 'a'];
    }
    int n = s.size();
    for (int i = 0; i < n; ++i) {
      if (cnt[s[i] - 'a'] == 1) {
        return i;
      }
    }
    return -1;
  }
};

func firstUniqChar(s string) int {
  cnt := [26]int{}
  for _, c := range s {
    cnt[c-'a']++
  }
  for i, c := range s {
    if cnt[c-'a'] == 1 {
      return i
    }
  }
  return -1
}

function firstUniqChar(s: string): number {
  const cnt = new Array(26).fill(0);
  for (const c of s) {
    cnt[c.charCodeAt(0) - 97]++;
  }
  for (let i = 0; i < s.length; i++) {
    if (cnt[s.charCodeAt(i) - 97] === 1) {
      return i;
    }
  }
  return -1;
}

/**
 * @param {string} s
 * @return {number}
 */
var firstUniqChar = function (s) {
  const cnt = new Array(26).fill(0);
  for (const c of s) {
    ++cnt[c.charCodeAt() - 'a'.charCodeAt()];
  }
  for (let i = 0; i < s.length; ++i) {
    if (cnt[s[i].charCodeAt() - 'a'.charCodeAt()] === 1) {
      return i;
    }
  }
  return -1;
};

class Solution {
  /**
   * @param String $s
   * @return Integer
   */
  function firstUniqChar($s) {
    for ($i = 0; $i < strlen($s); $i++) {
      $hashtable[$s[$i]]++;
    }
    for ($i = 0; $i < strlen($s); $i++) {
      if ($hashtable[$s[$i]] == 1) {
        return $i;
      }
    }
    return -1;
  }
}