(Problem from CodeSignal) Problem: Given a String s consisting of the alphabet only, return the first non-repeated element. Otherwise, return '-'. example: input - s="abacabad" output - 'c'
Following the code, I wrote in Java. However, only 16/19 cases have passed. Would there be a way to solve this problem in O(n) or O(1)?
char solution(String s) {
ArrayList<Character> hs = new ArrayList<>();
for (char c:s.toCharArray()) {
hs.add(c);
}
for (int j=0; j<s.length(); j ) {
if ( 1 == Collections.frequency(hs, s.charAt(j))) {
return s.charAt(j);
}
}
return '_';
}
CodePudding user response:
The minimal possible time complexity for this task is linear O(n), because we need to examine every character in the given string to find out whether a particular character is unique.
Your current solution runs in O(n^2) - Collections.frequency()
iterates over all characters in the string and this iteration and this method is called for every character. That's basically a brute-force implementation.
We can generate a map Map<Character,Boolean>
, which associates each character with a boolean
value denoting whether it's repeated or not.
That would allow to avoid iterating over the given string multiple times.
Then we need to iterate over the key-set to find the first non-repeated character. As the Map
implementation LinkedHashMap
is used to ensure that returned non-repeated character would be the first encountered in the given string.
To update the Map
I've used Java 8 method merge()
, which expects three arguments: a key, a value, and a function responsible for merging the old value and the new one.
public char solution(String s) {
Map<Character, Boolean> isNonRepeated = getMap(s);
for (Map.Entry<Character, Boolean> entry: isNonRepeated.entrySet()) {
if (entry.getValue()) {
return entry.getKey();
}
}
return '_';
}
public Map<Character, Boolean> getMap(String s) {
Map<Character, Boolean> isNonRepeated = new LinkedHashMap<>();
for (int i = 0; i < s.length(); i ) {
isNonRepeated.merge(s.charAt(i), true, (v1, v2) -> false);
}
return isNonRepeated;
}
In case if you're comfortable with streams, this problem can be addressed in one statement (the algorithm remains the same and time complexity would be linear as well):
public char solution(String s) {
return s.chars()
.mapToObj(c -> (char) c)
.collect(Collectors.toMap( // creates intermediate Map<Character, Boolean>
Function.identity(), // key
c -> true, // value - first occurrence, character is considered to be non-repeated
(v1, v2) -> false, // resolving values, character is proved to be a duplicate
LinkedHashMap::new
))
.entrySet().stream()
.filter(Map.Entry::getValue)
.findFirst()
.map(Map.Entry::getKey)
.orElse('_');
}
CodePudding user response:
One technique would be a 2 pass solution using a frequency/count array for each character.
public static char firstNonRepeatingChar(String s) {
int[] frequency = new int[26]; // this is O(1) space complexity because alphabet is finite of 26 letters
/* First Pass - Fill our frequency array */
for(int i = 0; i < s.length(); i ) {
frequency[s.charAt(i) - 'a'] ;
}
/* Second Pass - Look up our frequency array */
for(int i = 0; i < s.length(); i ) {
if(frequency[s.charAt(i) - 'a'] == 1) {
return s.charAt(i);
}
}
/* Not Found */
return '_';
}
This solution is O(2n) -> O(n) and a space complexity of O(1) because we are using a finite set of the English alphabet (26 letters). This wouldn't work in other scenarios for non-English alphabets.