Tuesday 2 February 2016

Remove Duplicate from String in Java

Design an algorithm and write code to remove the duplicate characters in a string without using any additional buffer.

To solve this problem, we can apply the same approach as we used to check the unique character in the string. Please check for the unique character in the string for better understanding of below given solution. 

Using one Boolean array:
package crack.coding.interview;
public class RemoveDuplicate {

     /**
      * Remove Duplicate using extra memory space.
      * @param str
      */
     public static void removeDuplicatesEff(char[] str) {
           int len = 0;
           if (str == null || (len = str.length)<2) {
                return;
           }
          
           boolean[] map = new boolean[256];

           for (int i = 1; i < len; ++i) {
                if (!map[str[i]]) {
                     map[str[i]] = true;
                } else {
                     str[i] = '0';
                }
           }
     }

     /**
      * Driver method top remove duplicate.
      * @param args
      */
     public static void main(String[] args) {
           String str = "removeduplicate";
           char[] array = str.toCharArray();
           removeDuplicatesEff(array);

           System.out.println(new String(array));
     }
}

Using only one extra variable:
package crack.coding.interview;
public class RemoveDuplicate {
     private static void removeDuplicate(char[] array) {
           int map = 0;
           for (int i = 0; i < array.length; i++) {
                int val = array[i] - 'a';

                /* Shift for Map bit position.
                 * Exp: For b val= 1 and the bit position after shifting 10,
                 * For c val= 2 and the bit position after shifting 100 */
                int bitPos = 1 << val;

                /* Check whether bit position already 1.
                 * If true: Set duplicate bit to zero. */
                if((map & bitPos)>0) {
                     array[i] = '0';
                }

                /* Modify the bit position in the array. */
                map = map | bitPos;
           }

     }

     /**
      * Driver method top remove duplicate.
      * @param args
      */
     public static void main(String[] args) {
           String str = "removeduplicate";
           char[] array = str.toCharArray();
           removeDuplicate(array);

           System.out.println(new String(array));
     }
}




No comments:

Post a Comment

Related Posts Plugin for WordPress, Blogger...