First Unique Character in a String
Statement
Given a string s, find the first non-repeating character and return its index. Return -1 if there’s no non-repeating character.
Constraints
- 1 ≤
s.length()≤ 10³ scontains lowercase English characters
Solution
"""
production algorithm
"""
from collections import Counter
class Solution:
def first_unique_character(self, s):
"""
time complexity O(n)
space complexity O(1)
"""
counter = Counter(s)
for i, c in enumerate(s):
if counter[c] == 1:
return i
return -1"""
unit tests
"""
from unittest import TestCase
from algorithms.counters.first_unique_character_in_string.solution import Solution
class SolutionTestCase(TestCase):
def test_zero_unique_characters(self):
# Given
string = "uuuvvvwwwxxxyyyzzz"
solution = Solution()
# When
actual = solution.first_unique_character(string)
# Then
expected = -1
self.assertEqual(actual, expected)
def test_some_unique_characters(self):
# Given
string = "rstuuuvvvwwwxxxyyyzzz"
solution = Solution()
# When
actual = solution.first_unique_character(string)
# Then
expected = 0
self.assertEqual(actual, expected)Strategy
Counters.
Explanation
First, the algorithm counts the frequencies of all characters of s. Then, the algorithm iterates the characters of s again. The first character found to have a frequency of one gets its index returned. Otherwise, all characters have a frequency greater than one, and so -1 is returned.
Time Complexity
At most, all characters of s are iterated twice. Therefore, the time complexity of the algorithm is O(n).
Space Complexity
At most, there are 26 unique characters in s since all characters are lowercase English characters. In other words, a constant number of a unique characters. Therefore, the auxiliary space complexity of the algorithm is O(1).
