Saturday, 28 May 2016

Find first non repeated character in a string



String is most important topic in Java.There are many programming question on String which are important from interview perspective.This is one of the problem where we need to find the first non repeated character in the String.There can be multiple solutions for this problem.One of the solution is as follows:-

Sample Program:-


import java.util.Hashtable;  
 public class FirstUnRepeatedCharacter {  
      private static Character getFirstUnRepeatedCharacterUsingHashTable(  
                char[] charArray) {  
           Hashtable<Character, Integer> hashtable = new Hashtable<Character, Integer>();  
           for (Character character : charArray) {  
                if (!hashtable.containsKey(character))  
                     hashtable.put(character, 0);  
                else  
                     hashtable.put(character, hashtable.get(character) + 1);  
           }  
           for (Character character : charArray) {  
                if (hashtable.get(character) == 0)  
                     return character;  
           }  
           return 0;  
      }  
      private static char getFirstUnRepaedtedCharacterUsingLoops(String str) {  
           int count;  
           for (int i = 0; i < str.length(); i++) {  
                count = 0;  
                for (int j = 0; j < str.length(); j++) {  
                     if (i != j && str.charAt(i) == str.charAt(j)) {  
                          count = count + 1;  
                          break;  
                     }  
                }  
                if (count == 0) {  
                     return str.charAt(i);  
                }  
           }  
           return 0;  
      }  
      public static void main(String[] args) {  
           String str = "daabbcc";  
           System.out.println("First Un repeated Character Using For loops:-"  
                     + getFirstUnRepaedtedCharacterUsingLoops(str));  
           System.out.println("First Un repeated Character Using HashTable:-"  
                     + getFirstUnRepeatedCharacterUsingHashTable(str.toCharArray()));  
      }  
 }  



The Time Complexity in case of First approach i.e. using for loops is O(n2) because each character is compared with remaining characters and 2 for loops are used for that to iterate over all the characters.
And The time Complexity for other approach i.e. using HashTable is O(2n) because first loop is used to insert the character in HashTable along with the count of character and Second loop is used to get the first unrepeated character.
First approach is preferable if given string is small and in case of large String we can use Second approach.



Enjoy Programming :)

1 comment:

  1. Why is preferable second approach if string is large?

    ReplyDelete