Finding and removing all duplicate in string unless they repeat an odd number of times

Question

I have been trying to solve this task for probably more than an hour already. I need to remove all the duplicates from a string but the tricky part is that if a letter is duplicated and odd number of times, one copy of that letter should remain in the final string. For example a string of assdafff should be converted to df because f is presented odd number of times. I managed to make a program to remove all duplicates but I cant find those that are presented an odd number of times there. It's important to keep the order of encountered elements in the output string the same like in the input.

 public static void main(String[] args){        
Scanner reader = new Scanner(System.in);
String x = reader.nextLine();
String ne = "";
StringBuffer buf = new StringBuffer(x.length() -1);
for(int i=0; i<x.length(); i++){
    for(int v = 0; v<x.length(); v++){
        if((x.charAt(i)==x.charAt(v))&&(i!=v)){
            break;
    }
    if((v==x.length()-1)&&(i!=v)){
        ne+=x.charAt(i);
    }}
}
if(ne.equals("")){
    System.out.println("Empty String");
}else{
System.out.println(ne);
}
}

score 2 · Answer 1 · answered Mar 06 '17 at 00:56

2

The algorithm is straightforward. As others have pointed, you could store the count for each character of the string in a map, and then keep only the entries of the map with an odd count. In order to preserve the insertion order, you should use a LinkedHashMap. Then, we merge the keys of the map into a new string.

A Java 8 solution could be as follows:

String string = "string-123-string";

Map<Integer, Long> map = string.chars()
        .boxed()
        .collect(Collectors.groupingBy(
                Function.identity(),
                LinkedHashMap::new,
                Collectors.counting()));

map.values().removeIf(count -> count % 2 == 0);

String result = map.keySet().stream()
        .map(i -> new char[] { (char) i.intValue() })
        .map(String::new)
        .collect(Collectors.joining());

System.out.println(result); // 123

answered Mar 06 '17 at 00:56

fps

33,623
8
55
110

When I test this code, eclipse bugs and gives me unknown error http://prntscr.com/egw4be – Mik Mar 06 '17 at 23:28
@Mik I believe that the bug is due to your `x` variable being `null` – fps Mar 07 '17 at 00:46
Or maybe it is because the code does not compile, i.e. you are missing the `LinkedHashMap` import statement, and there also seems to be an error with the package name... Is it named the same as the directory? Anyway, I tested my answer's code and everything works perfectly. – fps Mar 07 '17 at 00:50

nabil london · Accepted Answer · 2017-03-06T00:45:21.127

I'd use a Map like the other answers suggested, but the problem with it is that it doesn't store the key/value pairs in an ordered manner, so I used two ArrayLists to store the characters and their equivalent counts. Here's a working solution:

String string = "thisisastring";

StringBuffer buffer = new StringBuffer();
ArrayList<Character> chars = new ArrayList<>();
ArrayList<Integer> counts = new ArrayList<>();

for(int i= 0; i< string.length(); i++)
{
  char curChar = string.charAt(i);
  int charIndex;
  // if curChar already exists in chars, increment its count      
  if((charIndex = chars.indexOf(curChar))>-1) 
  {
    counts.set(charIndex, counts.get(charIndex)+1);
  }
  else // else add it to chars and add its count which is 1 to counts
  {
    chars.add(curChar);
    counts.add(1);
  }
}

for(int i= 0; i< chars.size(); i++)
  // if char count is odd, add it to the buffer
  if(counts.get(i)%2!=0)  
    buffer.append(Character.toString(chars.get(i)));

System.out.println(buffer.toString()); // prints hisarng

Edit: as @Federico Peralta Schaffner mentioned, you can also use a LinkedHashMap as follows:

String string = "thisisastring";
StringBuffer buffer = new StringBuffer();
LinkedHashMap<Character, Integer> linkedHashMap = new LinkedHashMap<>();

for(int i=0; i< string.length(); i++)
{
  char curChar = string.charAt(i);
  linkedHashMap.put(curChar, linkedHashMap.containsKey(curChar)?linkedHashMap.get(curChar)+1:1);
}

for(Map.Entry<Character, Integer> entry : linkedHashMap.entrySet())
  if(entry.getValue()%2 !=0)
    buffer.append(entry.getKey());

System.out.println(buffer.toString());  // prints hisarng

@FedericoPeraltaSchaffner Oh yes you're right, thanks for pointing out. — nabil london, Mar 06 '17 at 00:16
@FedericoPeraltaSchaffner I edited my answer to illustrate your suggestion if you don't mind ^^ — nabil london, Mar 06 '17 at 00:46

guillaume girod-vitouchkina · Answer 3 · 2017-03-07T21:10:25.213

0

1 iterate and use a Map< Char, Integer > to keep the counts.

2 iterate again and keep only chars with odd count

String string = "deadbeef";

// ALL COUNTS
Map<Character,Integer> counts=new HashMap<Character,Integer>();

for(int i= 0; i< string.length(); i++)
    {
  char c = string.charAt(i);

  if (counts.containsKey(c))
    counts.put(c,counts.get(c)+1);  
  else
      counts.put(c, 1);
  }

// RESULT
String result="";

// ALLREADY USED
Set<Character> set=new HashSet<Character>();

for(int i= 0; i< string.length(); i++)
    {
    char c = string.charAt(i);

        // ODD AND FIRST
      if ((counts.get(c)%2==1)
          &&(!set.contains(c)))
          result+=c;

     set.add(c);
    }   

System.out.println("RESULT:"+result);  // => eabf

edited Mar 07 '17 at 21:10

answered Mar 05 '17 at 22:20

guillaume girod-vitouchkina

3,061
1
10
26

What is map ? I had the idea of using separate for loops for finding odd duplicates but the final string should have the original positions of the letters – Mik Mar 05 '17 at 22:23
see https://docs.oracle.com/javase/7/docs/api/java/util/Map.html . You are a beginner, arent you ? – guillaume girod-vitouchkina Mar 05 '17 at 22:25
Why is this not working `Map m = new HashMap();` this is the map I defined and I add the elements but I cant remove them with this `for (Integer key : m.values()) { if(key%2==0){ m.remove(key); } }` – Mik Mar 06 '17 at 22:52
@Mik - I completed my solution (with Map and Set) . Other solutions work also. 1 in your code: you take key from values (Integer), but you use it to remove - 2 you cant iterate while you remove keys like that. See http://stackoverflow.com/questions/6092642/how-to-remove-a-key-from-hashmap-while-iterating-over-it – guillaume girod-vitouchkina Mar 07 '17 at 21:16

hikmathaji · Answer 4 · 2017-03-05T22:43:35.083

-1

You can solve this problem in just one iteration. First you need to save the locations of characters encountered for the first time. If you encounter them again delete the current one and the one you encountered earlier. For example, you have

s = "assdafff"

For all first encountered characters you save them by

for(i = 0; i<s.length(); i++)
  if(dict.get(s[i]) == null) //
    dict[s[i]] = i;

and else

else // which means it's duplicate
  delete both s[i] and s[dict.get(s[i])] from string

and don't forget to delete that current map entry as well.

edited Mar 05 '17 at 22:43

answered Mar 05 '17 at 22:31

hikmathaji

3
6

But what is dict ? – Mik Mar 05 '17 at 22:49
Sorry, forgot to mention, dictionary is the same data structure as map. Think of them as arrays but indexes can be anything other than integer. However, you can get away with just using arrays. I am pretty sure instead of `dict['a'] = 0`, you can use `dict[Character.getNumericValue('a')] = 0`. I hope this makes sese – hikmathaji Mar 05 '17 at 22:58
This question is about Java, you provided a python solution ^^ things are quite different between the two languages. – nabil london Mar 06 '17 at 00:00

Finding and removing all duplicate in string unless they repeat an odd number of times

4 Answers4