[DP] Find first non repeated character in a string [Rubicon]

1. Problem
Given a string, find the first non repeated character ?

2. Example
s= "hello", except 'l' all are non-repeated, but 'h' is the first non-repeated character.
s= "swiss", 'w' is the first non-repeated character.
One way to solve this problem is creating a table to store count of each character, and then picking the first entry which is not repeated. key thing to remember is order.

3. Implementation in Java

// Time:O(2n) two for loops not nested, Space:O(n) LinkedHashMap

// LinkedHashMap to store character count, since LinkedHashMap maintains // insertion order and we are inserting character in the order they 
// appear in the string.
// We just need to iterate through LinkedHashMap and choose the entry with value 1


public static char findFirstNonRepeatedCharacter( String s)
{
     Map map = new LinkedHashMap<>(str.length());
     for (char c: s.toCharArray())
     {
         map.put(c, map.containsKey(c)? map.get(c)+1 :1   );
     }
    
     for ( Entry entry:map.entrySet() )
     {
         if (entry.getValue() ==1)
         {
              return entry.getKey();
         }
     }
     throw new RuntimeException("cannot find any non repeated character");
}

4.Implementation in Java

// Time:O(n) one for loop, Space:O(n) set 

// one set and one list to repeating and non-repeating character separately
// Once we finish scanning through string, which is O(n), we can get the magic character by accessing List in O(1) time.

public static char findFirstNonRepeatedCharacter (String s)
{
    Set repeated = new HashSet<>();
    List nonRepeated = new ArrayList<>();
    for ( int i = 0 ; i < s.length() ; i++ )
    {
         char letter = s.charAt(i);
         if ( repeated.contains(letter)  ) 
         {
             continue;
         }
         if ( nonRepeated.contains( letter  )) 
         {
              nonRepeated.remove((Character) letter ));
              repeated.add( letter );
         }
         else
         {
              nonRepeated.add( letter );
         }
    }
    return nonRepeated.get(0);
}

5.Implementation in Java

// Time:O(2n) two for loops not nested, Space:O(n) 


// HashMap 

public static char findFirstNonRepeatedCharacter(String s)
{
    HashMap score = new HahMap<>();
    for ( int i = 0 ; i < s.length() ; i++)
    {
       char letter = s.charAt(i);
       score.put(letter, score.containsKey(letter)? score.get(letter)+1:1);  
    }

    for (int i = 0; i < s.length();i++)
    {
        char letter = s.charAt(i);
        if (score.get(letter) == 1)
        {
           return letter;
        }
    }
    throw new RuntimeException("Undefined Behavior");
}



import static org.junit.Assert.*;
import org.junit.Test;

public class findFirstNonRepeatedCharacterTest {

    @Test
    public void testFirstNonRepeatedCharacter() {
        assertEquals('b', Solution.firstNonRepeatedCharacter("abcdefghija"));
        assertEquals('h', Solution.findFirstNonRepeatedCharacter("hello"));
        assertEquals('J', Solution.findFirstNonRepeatedCharacter("Java"));
        assertEquals('i', Solution.findFirstNonRepeatedCharacter("simplest"));
    }

    @Test
    public void testFirstNonRepeatingChar() {
        assertEquals('b', Solution.firstNonRepeatingChar("abcdefghija"));
        assertEquals('h', Solution.findFirstNonRepeatedCharacter("hello"));
        assertEquals('J', Solution.findFirstNonRepeatedCharacter("Java"));
        assertEquals('i', Solution.findFirstNonRepeatedCharacter("simplest"));
    }

    @Test
    public void testGetFirstNonRepeatedChar() {
        assertEquals('b', Solution.getFirstNonRepeatedChar("abcdefghija"));
        assertEquals('h', Solution.findFirstNonRepeatedCharacter("hello"));
        assertEquals('J', Solution.findFirstNonRepeatedCharacter("Java"));
        assertEquals('i', Solution.findFirstNonRepeatedCharacter("simplest"));
    }
}

6. References:
http://javarevisited.blogspot.com/2014/03/3-ways-to-find-first-non-repeated-character-String-programming-problem.html