'First Unique Character in a String
Given a string, find the first non-repeating character in it and return its index. If it doesn't exist, return -1.
first_unique('leetcode') # 0
first_unique('loveleetcode') # 2
I came up with the following solution. How can I make it more efficient for very long input strings?
def first_unique(self, s):
if s == '':
return -1
for item in s:
if s.count(item) == 1:
return s.index(item)
break
return -1
Solution 1:[1]
My solution uses Counter form the collections module.
from collections import Counter
def first_unique(s):
c = Counter(s)
for i in range(len(s)):
if c[s[i]] == 1:
return i
return -1
Solution 2:[2]
Suave version:
from collections import Counter, OrderedDict
class OrderedCounter(Counter, OrderedDict):
pass
def first_unique(s):
counter = OrderedCounter(s)
try:
return counter.values().index(1)
except ValueError:
return -1
Weird version:
from collections import OrderedDict
def first_unique(s):
nah = {0}-{0} # funny pair of eyes
yeah = OrderedDict()
for i,c in enumerate(s):
if c not in nah:
try:
del yeah[c]
except KeyError:
yeah[c] = i
else:
nah.add(c)
return next(yeah.itervalues(), -1)
Solution 3:[3]
I would use a for loop to iterate the String from the beginning and at each index, I would check if the rest of the String has the character at the current index by using Substring.
Try this:
def firstUniqChar(word):
for i in range(0,len(word)): ## iterate through the string
if not word[i] in word[i+1:len(word)]: ## check if the rest contains that char
index=i
break
return index
Hope it helps!
Solution 4:[4]
The idea in this solution is to use a pair of defaultdicts. The first one contains an integer count of each character and the second contains the index location of the latest character read.
After reading all of the characters, a list comprehension is used to find all of those that only occurred once (result). The minimum index locations of these characters (found in our other defaultdict order) will give us the first index location of non-repeating characters.
from collections import defaultdict
# To Create random string:
from string import ascii_lowercase
from random import choice, randint, seed
# Create a random sentence of 1000 words (1-8 characters each).
seed(0)
gibberish = ' '.join(''.join(choice(ascii_lowercase)
for _ in range(randint(1, 8)))
for _ in range(1000))
print(len(gibberish))
# Output: 5614
# Solution.
def first_unique(s):
dd = defaultdict(int)
order = defaultdict(int)
for n, c in enumerate(s):
dd[c] += 1
order[c] = n
result = [order[c] for c in dd if dd[c] == 1]
return min(result) if result else -1
Timings
%timeit first_unique(gibberish)
100 loops, best of 3: 2.13 ms per loop
@wim solution:
%timeit first_unique(gibberish)
100 loops, best of 3: 5.06 ms per loop
@PatrickHaugh solution (which is much easier to understand than mine):
%timeit first_unique(gibberish)
100 loops, best of 3: 4.2 ms per loop
@BPL solution:
%timeit f1(gibberish)
10 loops, best of 3: 39.2 ms per loop
%timeit f2(gibberish)
1000 loops, best of 3: 890 µs per loop
Using a much shorter sentence of twenty words (133 characters):
%timeit first_unique(gibberish)
10000 loops, best of 3: 62.8 µs per loop
@wim solution:
%timeit first_unique(gibberish)
10000 loops, best of 3: 169 µs per loop
@PatrickHaugh solution:
%timeit first_unique(gibberish)
10000 loops, best of 3: 101 µs per loop
@BPL solution:
%timeit f1(gibberish)
10000 loops, best of 3: 55.1 µs per loop
%timeit f2(gibberish)
10000 loops, best of 3: 31 µs per loop
Test cases.
s1 = 'leetcode'
s2 = 'loveleetcode'
>>> first_unique(s1)
0
>>> first_unique(s2)
2
Solution 5:[5]
public class Main{
public static void main(String[] args) {
System.out.println("Input String : GirishRathi");
System.out.println("Output String : " +firstUniqChar("GirishRathi"));
}
public static int firstUniqChar(String s) {
Map<Character , Integer> map = new HashMap<Character , Integer>();
for(int i = 0 ; i < s.length() ; i++) {
char current = s.charAt(i);
if(map.containsKey(current)) {
map.put(current, -1);
}else {
map.put(current , i);
}
}
int min = Integer.MAX_VALUE;
for(char c : map.keySet()) {
if(map.get(c) > -1 && map.get(c) < min) {
min = map.get(c);
}
}
return min == Integer.MAX_VALUE ? -1 : min;
}
}
Solution 6:[6]
A first unique character in a string has below property.
- The starting index and end index of the character should be the same.
- Its starting index should be less than other unique character's starting index.
public int firstUniqChar(String s) {
int result = s.length();
for(char c = 'a'; c <= 'z'; c++){
int i = s.indexOf(c);
if(i != -1 && i == s.lastIndexOf(c)){
result = Math.min(result, i);
}
}
return result == s.length() ? -1 : result;
}
Solution 7:[7]
what about this approach?
def first_unique_letter(text):
for c in range(0, len(text)):
if text[c] not in text[0:c] and text[c] not in text[c + 1:len(text)]:
return text[c]
return "_"
it breaks the for cycle after finding the first unique letter, so it's better than wait for the entire cycle to finish. It returns a '_' when no character is unique
Solution 8:[8]
The below code iterates the string and checks if the character is present anywhere else in the string. Once found, it will skip the current character and move to the next.
def getUniqueCharacter(s):
for i in range(len(s)):
flag=0
for j in range(len(s)):
if i==j:
continue
if s[i]==s[j]:
flag=1
break
if flag==0:
return i
return -1
Solution 9:[9]
Newer python versions (>= 3.7) preserve insertion order in dicts and Counters.
def firstUniqChar(self, s: str) -> int:
for key in (ctr := Counter(s)):
if ctr[key] < 2:
return s.index(key)
return -1
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow
| Solution | Source |
|---|---|
| Solution 1 | Patrick Haugh |
| Solution 2 | |
| Solution 3 | codemirel |
| Solution 4 | |
| Solution 5 | |
| Solution 6 | Girija Sankar Panda |
| Solution 7 | Bjvandi Pohvak |
| Solution 8 | |
| Solution 9 | Abhyudaya Sharma |