How to delete those characters which have appeared more than once in a string in java?

Question

public class Main
{
  public static void main (String[]args)
  {
    String s = "Javaprogram";
    StringBuilder sb = new StringBuilder (s);
    String ans;
    int i, j;
    for (i = 0; i < sb.length (); i++)
      {
    for (j = i + 1; j < sb.length (); j++)
      {
        if (sb.charAt (i) == sb.charAt (j))
          {
        sb.deleteCharAt (i);
        sb.deleteCharAt (j);
          }
      }
      }

    System.out.println (sb.toString ());
  }
}

So I have written a code to delete those characters which have appeared more than once. For eg: If input is "Javaprogram", then first we should detect which characters have appeared multiple times and delete them. In this case, 'a' and 'r' have appeared twice so we should delete them. The output should be "Jvpogm". My logic seems to be correct.. but I don't why I am not able to get the answer.

Answer 1

As Johannes Klug referenced my suggestion in the text of his solution, and I had deleted the referenced comment I thought I better add it here.

The basic idea was to group each character with the frequency it occurs in the target string, once you have created the map you should remove all characters with a frequency less than your target frequency (in the OP's question two). Once you have filtered out non-targets you can then iterate over the target string again filtering out any characters that are found in your frequency map.

Turns out you dont need to filter the frequency map, as shown below:

    public static void main(String[] args) {
        String target = "Javaprogram";
        int targetFrequency = 2;

        Map<Integer, Integer> frequencyMap = new HashMap<>();

        for (int i = 0; i < target.length(); i++) {
            frequencyMap.compute(target.codePointAt(i), (key, v) -> (v == null) ? 1 : (v + 1));
        }

        String result = target.codePoints()
                .filter(cp -> frequencyMap.get(cp) < targetFrequency)
                .collect(StringBuilder::new, StringBuilder::appendCodePoint, StringBuilder::append)
                .toString();

    }

(Oddly it turns out that Java 15 doesn't have an Arrays.stream(char[]) method)

I am use frequencyMap.compute to replace the following if/else statement:

int key = target.codePointAt(i);
if (frequencyMap.containsKey(key)) {
    frequencyMap.put(key, frequencyMap.get(key) + 1);
} else {
    frequencyMap.put(key, 1);
}

As I said in my original comments the solution will largely depend on what it is you are attempting to achieve, the advantage of this method is you have a frequency map which you can use to perform other queries, about the frequency of letters in the target string.

Answer 2

For regex fans:

String s = "Javaprogram";
int i;
while ((i = s.replaceFirst("([a-zA-Z]).*\\1","_").indexOf("_")) >= 0) s = s.replaceAll(s.substring(i,i+1),"");
System.out.println(s);

prints

Jvpogm

Of course, this solution requires a character which cannot exist in the original input String. And change the matching character class as needed - currently alphabetics.

Answer 3

Here is my solution using a Set data structure. Essentially a Set cannot hold duplicate values. By exploiting this property of a Set I can identify duplicate values in a String. Then, I simply use the replace method to remove the duplicate characters.

public static void main( String[] args ) {

    String str = removeDuplicates("Javaprogram");
    
    System.out.println( str );
}

private static String removeDuplicates( String str ) {
    
    final Set<Character> temp = new HashSet<Character>();
    
    for( final char c : str.toLowerCase().toCharArray() ) {
        if( !temp.add(c) ) {
            str = str.replace( Character.toString(c), "" );
        }
    }
    
    return str;
}

Answer 4

My approach is to create a new string out from the input considering the character frequency.

public static void main(String[] args) {
    String input = "Javaprogram";
    List<String> inputArr = Arrays.asList(input.split(""));
    
    List<String> outputArr = inputArr.stream().filter(i -> countCharacters(i, inputArr) == 1).collect(Collectors.toList());
    String output = String.join("", outputArr);

    System.out.println(output); //Jvpogm
}

public static int countCharacters(String chr, List<String> strArr) {
    return (int) strArr.stream().filter(i -> i.equals(chr)).count();
}

Answer 5

First of all, like Johnny Mopp pointed out:

sb.charAt(i + 1). Should be sb.charAt(j)

however, this won't fix the application, as you're also concurrently modifying the Stringbuilder, so you'd also need to do "sb.deleteCharAt(j - 1);" as the index was moved by the statement before, and then you'd need to not increment j... But all of this is super inefficient and hacky. and can't remove uneven numbers of the same character -> if the first two "a"s are removed the program will leave the last "a" in there

A better approach would be to iterate the string once, and check if the character doesn't appear somewhere else. e.g. by using input.indexOf(c) == input.lastIndexOf(c). If this is true, add it to the result.

Example:

String input = "Javaprogram";
String output = input.codePoints()
            .filter(c -> input.indexOf(c) == input.lastIndexOf(c))
            .collect(StringBuilder::new, StringBuilder::appendCodePoint, StringBuilder::append)
            .toString();
System.out.println(output);

Edit: The approach of Gavin with filling a map is probably more efficient but has more code. As your program is probably only relevant for short strings (otherwise there will likely be no character left) efficiency is not really important here though.

Edit 2: The most performance optimized approach I can come up with is this:

String input = "Javaprogram";
Set<Character> handledChars = new HashSet<>();
StringBuilder sb = new StringBuilder();
char[] chars = input.toCharArray();
for (int i = 0; i < chars.length; i++) {
    char c = chars[i];
    if (handledChars.add(c)) {
        int hits = 0;
        for (int j = i + 1; j < chars.length && hits == 0; j++) {
            if (chars[j] == c) {
                hits++;
            }
        }
        if (hits == 0) {
            sb.append(c);
        }
    }
}
System.out.println(sb);

Answer 6

Here is the answer:

public class JavaProgram {
    public static void main(String[] args) {
        String s = "Javaprogram";
        String ans = "";
        for (int i = 0; i < s.length(); i++) {
            String substring = s.substring(i, i + 1);
            if (!s.substring(0,i).concat(s.substring(i+1)).concat(ans).contains(substring)) {
                ans += substring;
            }
        }
        System.out.println(ans);
    }
}

Output:

Jvpogm

Answer 7

Deleting characters while iterating the String causes the String length to change. All characters that come after the deleted index will move down one index. So to circumvent this, I'll iterate the String from the back:

public static void main(String[] args) {
    String s = "Javaprogram";
    StringBuilder sb = new StringBuilder(s);
    for(int i = sb.length() - 1; i >= 0; i--) {
        boolean duplicate = false;
        for(int j = i - 1; j >= 0; j--) {
            if(sb.charAt(j) == sb.charAt(i)) {
                duplicate = true; // A duplicate character was found
                sb.deleteCharAt(j);
                i--; // Update i to keep up with the changed String length
            }
        }

        // If a duplicate was found, the original must be deleted as well
        if(duplicate) {
            sb.deleteCharAt(i);
        }
    }

    System.out.println(sb.toString());
}

The String length is changing, that's why you still need to update i, whenever a duplicate character was deleted, otherwise the index will be out of range.

Running this will give you Jvpogm as desired.