1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
|
<<-DOC
Note: Write a solution that only iterates over the string once and uses O(1) additional memory,
since this is what you would be asked to do during a real interview.
Given a string s, find and return the first instance of a non-repeating character in it.
If there is no such character, return '_'.
Example
For s = "abacabad", the output should be
firstNotRepeatingCharacter(s) = 'c'.
There are 2 non-repeating characters in the string: 'c' and 'd'.
Return c since it appears in the string first.
For s = "abacabaabacaba", the output should be
firstNotRepeatingCharacter(s) = '_'.
There are no characters in this string that do not repeat.
Input/Output
[time limit] 4000ms (rb)
[input] string s
A string that contains only lowercase English letters.
Guaranteed constraints:
1 ≤ s.length ≤ 105.
[output] char
The first non-repeating character in s, or '_' if there are no characters that do not repeat.
DOC
describe "first_non_repeating_character" do
def first_non_repeating_character(message)
chars = message.chars
hash = chars.inject(Hash.new(0)) { |memo, char| memo[char] += 1; memo }
chars.each do |char|
if hash[char] <= 1
return char
end
end
"_"
end
[
{ s: "abacabad", x: "c" },
{ s: "abacabaabacaba", x: "_" },
{ s: "z", x: "z" },
{ s: "bcb", x: "c" },
{ s: "bcccccccb", x: "_" },
{ s: "abcdefghijklmnopqrstuvwxyziflskecznslkjfabe", x: "d" },
{ s: "zzz", x: "_" },
{ s: "bcccccccccccccyb", x: "y" },
{ s: "xdnxxlvupzuwgigeqjggosgljuhliybkjpibyatofcjbfxwtalc", x: "d" },
{ s: "ngrhhqbhnsipkcoqjyviikvxbxyphsnjpdxkhtadltsuxbfbrkof", x: "g" },
].each do |x|
it do
expect(first_non_repeating_character(x[:s])).to eql(x[:x])
end
end
end
|
