Removing duplicate characters from string recursively

Question

I need help to understand how I can remove duplicate characters from a string. This needs to be done recursively, which is the real problem.

public class FEQ2 { /** * @param args */ public static void removeDups(String s, int firstChar, int secondChar) { if (s.length() == 1) { System.out.println(s); } char a = s.charAt(firstChar); if (a == s.charAt(secondChar)) { s = a + s.substring(secondChar + 1); } System.out.println(s); removeDups(s, firstChar + 1, secondChar + 1); //return s; } public static void main(String[] args) { //System.out.println(removeDups("AAAABBARRRCC", 1)); removeDups("AAAABBARRRCC", 0 , 1); } } 

Answer 1

You can do it as follows:

 public static String removeDups(String s) { if ( s.length() <= 1 ) return s; if( s.substring(1,2).equals(s.substring(0,1)) ) return removeDups(s.substring(1)); else return s.substring(0,1) + removeDups(s.substring(1)); } INPUT: "AAAABBARRRCC" OUTPUT: "ABARC" 

================

EDIT: another way

 public static String removeDups(String s) { if ( s.length() <= 1 ) return s; if( s.substring(1).contains(s.substring(0,1)) ) return removeDups(s.substring(1)); else return s.substring(0,1) + removeDups(s.substring(1)); } INPUT: "AAAABBARRRCC" OUTPUT: "BARC" 

===============

EDIT: third way

 public static String removeDups(String s) { if ( s.length() <= 1 ) return s; if( s.substring(0,s.length()-1).contains(s.substring(s.length()-1,s.length())) ) return removeDups(s.substring(0,s.length()-1)); else return removeDups(s.substring(0,s.length()-1)) + s.substring(s.length()-1,s.length()); } INPUT: "AAAABBARRRCC" OUTPUT: "ABRC" 

Answer 2

The general trick to doing something recursively is to take all the variables and turn them into parameters and change all assignments to function calls. You may need more than one function for more complex things, but usually you can easily flip each loop into a tail-recursive function :

 function(){ int i=0; int x=0; //initialize while(condition){ x = x+i; //update i = i+1; } return x; } 

becomes

 function(i,x){ //variables are now parameters if(condition){ return x; }else{ return function(i+1, x+i); //update } } main(){ function(0,0); //initialize 

================

Here is the duplicate removal code, for example, for example (it does not do the same as yours)

 removeDuplicates(str): i = str.length-1; out_str = ""; chars_used = [] while(i >= 0): c = str[i] if(c not in chars_used): chars_used.append(c) out_str += c i -= 1 return out_str 

becomes

 remove_duplicates(str, i, out_str, chars_used): if i < 0: return out_str else: c = str[i] if c in chars_used: return remove_duplicates(str, i-1, out_str, chars_used) else: return remove_duplicates(str, i-1, out_str+c, chars_used+[c]) 

Answer 3

Will it help you?

  public static String getUniqueChars(String realString) { StringBuilder resultString = null; try { List<Character> characterArray = new <Character> ArrayList(); for(char c : realString.toCharArray()) { characterArray.add(c); } resultString = new StringBuilder(); for(Character c : new TreeSet<Character>(characterArray)) { resultString.append(c.charValue()); } } catch (Exception e) { e.printStackTrace(); } resultString.toString(); } 

Answer 4

 private static String removeChars(String s) { int n= s.length(); int i= 0; int j= 1; Map<Integer, Boolean> mark= new HashMap<>(); while(j<n) { if(s.charAt(i)== s.charAt(j)) { mark.put(i, true); mark.put(j, true); if(i== 0) { i= j+1; j= i+1; } else { i= i-1; j= j+1; } } else { i= j; j= j+1; } } String str= ""; for(int k= 0;k<n;k++) { if(!mark.containsKey(k)) { str+= s.charAt(k); } } return str; }