javastringalgorithmarraylistcollections

First non-repeating character in a stream of characters


The question asks us to find new string B.

B is formed such that we have to find first non-repeating character each time a character is inserted to the stream and append it at the end to B. If no non-repeating character is found then append '#' at the end of B.

Example:
    "a"      -   first non repeating character 'a'
    "ab"     -   first non repeating character 'a'
    "aba"    -   first non repeating character 'b'
    "abad"   -   first non repeating character 'b'
    "abadb"  -   first non repeating character 'd'
    "abadbc" -   first non repeating character 'd'

Can someone help me out where my code went wrong. my logic is to use substring function of string and find the unique character and add it to arraylist and print the entire arraylist.

public class Solution
{
    public String solve(String A) 
    {
        ArrayList<Character>a=new ArrayList<Character>();
        String res="";

        for(int i=0;i<A.length();i++)
        { 
            String ss=A.substring(0,i+1);
            String ue=uniqueCharacters(ss);
           // System.out.println(ue);
      
           if(ue!="") a.add(ue.charAt(0));
           else a.add('#');
        } 
     
        for(Character j:a) res+=j;
    
        return res;
    } 

    public static String uniqueCharacters(String test)
    {
        String temp = "";
    
        for (int i = 0; i < test.length(); i++)
        {
            char current = test.charAt(i);
            if (temp.indexOf(current) < 0) temp = temp + current;
            else temp = temp.replace(String.valueOf(current), "");
        }

        return temp;
    }
}    

Solution

  • It may be better to use a Set to detect unique characters in the input string using the result of Set::add which returns false if no element has been actually added to the set, and a Queue to maintain the non-repeated characters.

    When a repeated (non-unique) character is detected, it gets removed from the queue and if necessary, "#" is applied as a placeholder. And if a unique character is detected, it is just added to the queue.

    Example implementation:

    public static String solve(String str) {
        // verify the input
        if (null == str || str.isEmpty()) {
            return str;
        }
        
        Set<Character> previous = new LinkedHashSet<>();
        Queue<Character> nonRepeated = new LinkedList<>();
        
        StringBuilder sb = new StringBuilder();
    
        // use the first character
        char curr = str.charAt(0);
        previous.add(curr);
        nonRepeated.add(curr);
        sb.append(curr);
        
        for (int i = 1, n = str.length(); i < n; i++) {
            char c = str.charAt(i);
            
            if (!previous.add(c)) { // duplicate character found
                nonRepeated.remove(c);
                if (nonRepeated.isEmpty()) {
                    curr = '#';
                } else { // get the next non-repeated character
                    curr = nonRepeated.peek();
                }
            } else { // unique element is detected
                if (curr == '#') {
                    curr = c;
                }
                nonRepeated.add(c);
            }
            
            sb.append(curr);
        }
        
        return sb.toString();
    }
    

    Tests:

    for (String t : Arrays.asList("abadbc", "abcdba", "aaabbbacab")) {
        System.out.printf("input: %s --> %s%n----%n", t, solve(t));
    }
    

    Output:

    input: abadbc --> aabbdd
    ----
    input: abcdba --> aaaaac
    ----
    input: aaabbbacab --> a##b###ccc
    ----