Convert the string so it holds only distinct characters

Convert the string so it holds only distinct characters

Question

Given a string convert that to a string which holds only distinct characters. Also, find the number of character to be changed to make the string distinct. Change only the characters that are not distinct. Output must be as follows…

 

Logic

  • First, check each character for the count. If they appear more than once find the alternative.
  •  The alternative character must be distinct (must not be already present in the string)
  • It is not possible to have distinct characters( only a to z ) if the given string is of length more than 26.

Alternative

  1. Create ‘unique‘ Set to store all the distinct elements. Set doesn’t allow to store duplicate elements. See here for more Set related programs.   Create a new ‘result‘ set
  2. Check each character whether they are present in the ‘result’ Set(set to store result).
  3. If not present add to ‘result‘ Set.
  4. If the character is present in ‘result’ set, check for the alternative from a to z.
  5. Add the alternative character to both the Sets. Increase the count of no of characters changed.

Program

[code lang=”java”]
import java.util.HashSet;
import java.util.Set;

class MinChar
{
public static void main(String vr[])
{
String arr =new String("bbcaacgkkk");
char ch[]= arr.toCharArray(); //string to char for indexing
char c;
int count = 0; //number of changes
Set<Character> unique = new HashSet();
Set<Character> result= new HashSet();
String str="";
int ln = arr.length();

//creating unique set
for (int j =0; j<ln;j++)
unique.add(ch[j]); //add distinct character to set

if(ln>26)
System.out.println("Not possible");
else
{
for(int k=0;k<ln;k++)
{ //if element appears for first time
if(!result.contains(ch[k])) //result doesn’t contains
{ result.add(ch[k]);
str +=ch[k]; //append to result string
}
else //if element present
{
//finding another distinct char
for(c =’a’;c<=’z’;c++)
{ if(!unique.contains(c)) //not present in unique
{
count++; //no of char to be changed
result.add(c);
unique.add(c); //useful to compare next time
str =str+c;
break; //very important
}
}
}
}

System.out.println(str);
System.out.println("Changed : "+count);
}

}

}</pre>
[/code]

Sree Hari Sanjeev

The founder of Wisdom Overflow. Software Developer at Zoho Corporation.

Leave a Reply

Your email address will not be published. Required fields are marked *