Monday, July 17, 2017

Remove duplicate characters from String


/**
 * Problem :- Design an algorithm and write code to remove the duplicate characters in a string without using any 
 * additional bu er. NOTE: One or two additional variables are  ne. An extra copy of the array is not.
 */
public class RemoveDuplicates {
    /*
    If the duplicate characters are contiguous
     */
    public void removeDuplicates(char[] str) {
        if (str == null || str.length < 2)
            return;

        int writeIndex = 1;
        for (int i = 1; i < str.length; i++) {
            if (str[i] != str[i - 1]) {
                str[writeIndex++] = str[i];
            }
        }
        for (int i = writeIndex; i < str.length; i++) {
            str[i] = '0';
        }
    }

    /*
    If the duplicate characters are non duplicate then we should manintain a HashSet/boolean array to remember
    the characters that we have seen so far and not copy them again
     */
    public void removeDuplicates2(char[] str) {
        if (str == null || str.length < 2)
            return;
        boolean[] charHit = new boolean[256];
        int writeIndex = 0;
        for(int i = 0 ; i < str.length; i++){
            int currentChar = Character.getNumericValue(str[i]);
            if(charHit[currentChar])
                continue;
            str[writeIndex++] = str[i];
            charHit[currentChar] = true;
        }
        for (int i = writeIndex; i < str.length; i++) {
            str[i] = '0';
        }
    }
}

No comments:

Post a Comment