possible solution to find non-repeated character in a string
package findFirstRepeatedCharInString;
import java.util.HashMap;
import java.util.LinkedHashSet;
import java.util.Map;
import java.util.Set;
public class findFirstNonRepeatedCharInString {
/*=================================Solution1=========================*/
public static char firstNonRepeatingCharacterInString1(String str) {
boolean found;
char[] chars = str.toCharArray();
for (int i = 0; i < chars.length; i++) {
found = false;
for (int j = 0; j < chars.length; j++) {
found = (i != j) && (chars[i] == chars[j]);
if (found) {
break;
}
}
if (!found) {
return chars[i];
}
}
return '-';
}
/*===================================solution2========================*/
public static char firstNonRepeatingCharacterInString2(String str) {
Set<Character> chSet = new LinkedHashSet<Character>();
char[] charArray = str.toCharArray();
for (int i = 0; i < charArray.length; i++) {
if (!chSet.add(charArray[i])) {
chSet.remove(charArray[i]);
}
}
if (chSet.isEmpty())
return '-';
else
return (Character) (chSet.toArray())[0];
}
/*=============================================================*/
/*============================solution 3===============================*/
/* To find first non repeating character in a string
* eg: if string is 'total' then 'o' is the answer
* eg: if string is 'tweetwer' then 'r' is the answer
* time complexity :
* space complexity;
*/
public static char firstNonRepeatingCharacterInString3(String s) {
if (s == null)
return '-';
Map<String, Integer> inputMap = new HashMap<String, Integer>();
for(int i=0; i < s.length(); i++) {
String key = s.substring(i, i+1);
if (inputMap.get(key) == null) {
inputMap.put(key, new Integer(0));
}
else {
int it = inputMap.get(key)+1;
inputMap.put(key, it);
}
}
//Now start from the start of the string and find the character which has count 1
// first in order from left to right
boolean found = false;
String nonRepeatingStr = null;
for(int i=0; i < s.length(); i++) {
String key = s.substring(i, i+1);
if(inputMap.get(key) == 0) {
nonRepeatingStr = key;
found= true;
break;
}
}
if(found){
return nonRepeatingStr.toCharArray()[0];
}
return '-';
}
/*==============================================================*/
public static void main(String[] args) {
System.out.println(firstNonRepeatingCharacterInString1("abcxafabc"));
System.out.println(firstNonRepeatingCharacterInString2("abcxafabc"));
System.out.println(firstNonRepeatingCharacterInString3("abcxafabc"));
System.out.println("====================================");
System.out.println(firstNonRepeatingCharacterInString1("tweetwer"));
System.out.println(firstNonRepeatingCharacterInString2("tweetwer"));
System.out.println(firstNonRepeatingCharacterInString3("tweetwer"));
System.out.println("====================================");
System.out.println(firstNonRepeatingCharacterInString1("total"));
System.out.println(firstNonRepeatingCharacterInString2("total"));
System.out.println(firstNonRepeatingCharacterInString3("total"));
}
}
