First non-repeating character in a stream of characters

Question

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;
    }
}    

Answer 1

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
----