Popular Posts

Thursday, February 16, 2012

Second non repeating character

For a given a string, find its second non-repeating character.
public class SecondNonRepeatingCharacter {
/**
* Prints second non repeating character. O(N) time complexity O(1) space
* complexity
*
* @param args
*/
public static void main(String[] args) {
String str = "nonrepeatingcharacter";
// in the above string first non repeating character is o
// second one is p

// create an array to store char count
int[] charCount = new int[26];

// scan the string and store each character count.
for (int i = 0; i < str.length(); i++) {
charCount[str.charAt(i) - 'a']++;
}

int nonRepeatingCharcter = 0;
for (int i = 0; i < str.length(); i++) {
int index = str.charAt(i) - 'a';
if (charCount[index] == 1) {
nonRepeatingCharcter++;
if (nonRepeatingCharcter == 2) {
System.out.println("Secondnon repeating character : "
+ str.charAt(i));
break;
}
}
}

// prints how many times each character is repeated.duplicates are
// allowed
// for (int i = 0; i < str.length(); i++) {
// int index = str.charAt(i) - 'a';
// if (charCount[index] > 0)
// System.out.println("char : " + str.charAt(i) + " repeated : "
// + charCount[index] + " times.");
// }

}
}

No comments:

Post a Comment