Data Structures and Algorithms: Problem Name: Removing duplicate characters from character array (Solution in Java)

/*

* Problem: Design an algorithm and write code to remove the duplicate characters in a string

* without using any additional buffer. NOTE: One or two additional variables are fine.

* An extra copy of the array is not.

*

FOLLOW UP

Write the test cases for this method.

Solution:

1. For each character, check if it is a duplicate of already found characters.

2. Skip duplicate characters and update the non duplicate characters.

Page: 91

Time complexity is O(n pow 2)

*/

package ds;

public class RemoveDuplicateChars {

public static void main(String[] args) {

System.out.println("Example 1");

char[] str = {‘a’,’b’,’c’,’d’,’e’,’f’ };

removeDuplicate(str);

System.out.println(str); //abcdef

System.out.println("Example 2");

char[] str1 = {‘a’,’a’,’b’,’c’,’d’,’e’,’d’,’d’,’f’,’f’ };

removeDuplicate(str1);

System.out.println(str1); //abcdef

}

private static void removeDuplicate(char[] str)

{

if(str == null)

return;

if(str.length < 2)

return;

int len = str.length;

for(int i = 1; i < len; ++i)

{

int j = 0;

for(j = 0; j < i; ++j)

{

if(str[i] == str[j])

{

for(int k = i; k < len-1; k++) //Shift the elements to left.

str[k] = str[k+1];

i = i – 1; //shift the value of i, since i could contain the new value at the same location due to shifting.

len = len-1; //Reduce the string length, since we have shifted the elements by 1

str[len] = ”; //Set the last index of the char array to null.

}

}

}

System.out.println("Inside remove duplicate: " + str);

System.out.println(str);

System.out.println(len); //Final length of the string after removing duplicate characters.

}

}

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s