Teaching Kids Programming: Videos on Data Structures and Algorithms
Given a string s, return the first non-repeating character in it and return its index. If it does not exist, return -1.
Example 1:
Input: s = “leetcode”
Output: 0Example 2:
Input: s = “loveleetcode”
Output: 2Example 3:
Input: s = “aabb”
Output: -1Constraints:
1 <= s.length <= 10^5
s consists of only lowercase English letters.
Python Program to Get First Unique Character
Bruteforce may work: checking each character to see if it is unique – this requires O(N^2) time but O(1) space.
1 2 3 4 5 6 7 8 9 10 11 12 | class Solution: def firstUniqChar(self, s: str) -> int: n = len(s) for i in range(n): unique = True for j in range(n): if i != j and s[i] == s[j]: unique = False break if unique: return i return -1 |
class Solution: def firstUniqChar(self, s: str) -> int: n = len(s) for i in range(n): unique = True for j in range(n): if i != j and s[i] == s[j]: unique = False break if unique: return i return -1
We can use a Counter (O(N) space) to count the character frequencies, and iterate over the string again using enumerate function. And return the first index of the unique character.
1 2 3 4 5 6 7 | class Solution: def firstUniqChar(self, s: str) -> int: a = Counter(s) for i, j in enumerate(s): if a[j] == 1: return i return -1 |
class Solution: def firstUniqChar(self, s: str) -> int: a = Counter(s) for i, j in enumerate(s): if a[j] == 1: return i return -1
The time and space complexity is O(N) – where N is the number of the characters in the given string. If the input string is only lowercase characters, the space complexity is O(1) – as we can also use a static array of size 26 to count the number of appearances for lowercases only.
1 2 3 4 5 6 7 8 9 | class Solution: def firstUniqChar(self, s: str) -> int: a = [0] * 26 for i in s: a[ord(i) - 97] += 1 for i, j in enumerate(s): if a[ord(j) - 97] == 1: return i return -1 |
class Solution: def firstUniqChar(self, s: str) -> int: a = [0] * 26 for i in s: a[ord(i) - 97] += 1 for i, j in enumerate(s): if a[ord(j) - 97] == 1: return i return -1
ord function gets the ASCII code of a character.
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: A Pseudo Random Generator in Java to Shuffle an Array/List
Next Post: GoLang: Command Line Tool to Sort Strings