First non repeated character in string
Given a string, find first non repeated character in a string. For example, string is abcbdbdebab, the first non repeating character would be c. Even though e is also non repeating in string, c is output as it is first non repeating character.
Non repeating character : thoughts
What does it mean to be non-repeating character? Well, the character should occur in string only once. How about we scan the string and find what is count for each character? Store character and count in map as key value pair.
Now, that we have <character, count> key value pair for all unique characters in string, how can we find first non repeating character? Refer back to original string; scan the string again and for each character, check the corresponding count and if it is 1 return the character.
package com.company;
import java.util.HashMap;
/**
* Created by sangar on 4.10.18.
*/
public class FirstNonRepeatingChar {
HashMap<Character, Integer> characterCount = new HashMap<>();
public char firstNonRepeatingCharacter(String s){
//Best to discuss it with interviewer, what should we return here?
if(s == null) return ' ';
if(s.length() == 0) return ' ';
for (char c: s.toCharArray()){
if(!characterCount.containsKey(c)){
characterCount.put(c,1);
}
else {
characterCount.put(c, characterCount.get(c) + 1);
}
}
for (char c: s.toCharArray()) {
if(characterCount.get(c) == 1) return c;
}
return ' ';
}
}
package test;
import com.company.FirstNonRepeatingChar;
import org.junit.jupiter.api.Test;
import static org.junit.jupiter.api.Assertions.assertEquals;
/**
* Created by sangar on 28.8.18.
*/
public class FirstNonRepeatingCharTest {
FirstNonRepeatingChar tester = new FirstNonRepeatingChar();
@Test
public void firstNonRepeatingCharExists() {
String s = "abcbcbcbcbad";
assertEquals('d', tester.firstNonRepeatingCharacter(s));
}
@Test
public void firstNonRepeatingCharDoesNotExists() {
String s = "abcbcbcbcbadd";
assertEquals(' ', tester.firstNonRepeatingCharacter(s));
}
@Test
public void firstNonRepeatingCharWithEmptyString() {
String s = "";
assertEquals(' ', tester.firstNonRepeatingCharacter(s));
}
@Test
public void firstNonRepeatingCharWithNull() {
assertEquals(' ', tester.firstNonRepeatingCharacter(null));
}
}
Complexity of this method to find first non-repeating character in a string is O(n) along with space complexity of O(1) to store the character to count map.
There is always some confusion about space complexity of above method, we think as 256 characters are used, should it not be counted as space complexity? Definitely. But in asymptotic notations, this space is independent of size of input, so space complexity remains O(1).
One more thing, even though time complexity is O(n), input string is scanned twice, first time to get count of characters and second time to find first non repeating character.
Optimization
Consider a case when string is too large with millions of characters, most of them repeated, above solution may turn slow in last where we look for character with count 1 in map. How can we avoid scanning array second time?
How about we store some information with character in map along with count, so that we can figure out if the character is first non repeating or not.
Or we can have two maps, one stores the count and other stores the first index of character.
Once, we have created two maps as mentioned above, go through the first map and find the all characters with count 1. For each of these characters, check which one has the minimum index on second map and return that character.
Complexity of algorithm remains same, however, second scan of string is now not required. In other words, second scan is now independent of size of input as it depends on the size of first map, which is constant to 256 as that’s the number of unique 8 bit characters possible.
Find first non repeating character : Implementation
package com.company;
import java.util.HashMap;
/**
* Created by sangar on 4.10.18.
*/
public class FirstNonRepeatingChar {
public char firstNonRepeatingCharacterOptimized(String s){
HashMap<Character, Integer> characterCount = new HashMap<>();
HashMap<Character, Integer>characterIndex = new HashMap<>();
//Best to discuss it with interviewer, what should we return here?
if(s == null) return ' ';
if(s.length() == 0) return ' ';
for (int i=0; i<s.length(); i++){
char c = s.charAt(i);
if(!characterCount.containsKey(c)){
characterCount.put(c,1);
characterIndex.put(c,i);
}
else {
characterCount.put(c, characterCount.get(c) + 1);
}
}
char nonRepeatedCharacter = ' ';
int prevIndex = s.length();
for (char c : characterCount.keySet()) {
if(characterCount.get(c) == 1
&& characterIndex.get(c) < prevIndex){
prevIndex = characterIndex.get(c);
nonRepeatedCharacter = c;
}
}
return nonRepeatedCharacter;
}
}
package test;
import com.company.FirstNonRepeatingChar;
import org.junit.jupiter.api.Test;
import static org.junit.jupiter.api.Assertions.assertEquals;
/**
* Created by sangar on 28.8.18.
*/
public class FirstNonRepeatingCharTest {
FirstNonRepeatingChar tester = new FirstNonRepeatingChar();
@Test
public void firstNonRepeatingOptimizedCharExists() {
String s = "aebcbcbcbcbad";
assertEquals('e', tester.firstNonRepeatingCharacterOptimized(s));
}
@Test
public void firstNonRepeatingCharOptimizedDoesNotExists() {
String s = "abcbcbcbcbadd";
assertEquals(' ', tester.firstNonRepeatingCharacterOptimized(s));
}
@Test
public void firstNonRepeatingCharOptimizedWithEmptyString() {
String s = "";
assertEquals(' ', tester.firstNonRepeatingCharacterOptimized(s));
}
@Test
public void firstNonRepeatingCharOptimizedWithNull() {
assertEquals(' ', tester.firstNonRepeatingCharacterOptimized(null));
}
}
Please share if there is anything wrong or missing. If you are interested in taking personalized coaching sessions by our expert teachers, please signup to website and get first session free.