CODEWITHSUNDEEP
stringalgorithm
Soumya Kanti Naskar
Soumya Kanti Naskar

Reputation: 1081

Algorithm to delete duplicate characters from a String

Let us a have a string "abbashbhqa". We have to remove the duplicate characters in such a manner that the output should be "abshq". One possible solution is to check each character with the others present in the string and then manipulate. But this requires O(n^2) time complexity. Is there any optimised approach to do so ?

Upvotes: 1

Views: 96

Answers (4)

Roushan kumar
Roushan kumar

Reputation: 1

I am solving using Python and it works in O(n) time and O(n) space -- I am using set() as set does not allow duplicates --- In this case the order of elements gets changed -- If u want the order to remain same then u can use OrderedDict() and it also works in O(n) time --

def remove_duplicates(s , ans_set):     
    for i in s:                  # O(n)
        ans_set.add(i)           # O(1)
    ans = ''
    for char in ans_set:
        ans += char
    print ans

s = raw_input()
ans_set = set()
remove_duplicates(s , ans_set)

from collections import OrderedDict
def remove_duplicates_maintain_order(a):                 
    ans_dict = OrderedDict()
    for i in a:                                         # O(n)
        ans_dict[i] = ans_dict.get(i , 0) + 1           # O(1)
    ans = ''
    for char in ans_dict:
            ans += char
    print ans

s = raw_input()
remove_duplicates_maintain_order(s)

Upvotes: 0

Soumya Kanti Naskar
Soumya Kanti Naskar

Reputation: 1081

Probably this will be the implementation of the above problem

import java.util.*;
import java.io.*;

public class String_Duplicate_Removal
{

    public static String duplicate_removal(String s)
    {
        if(s.length()<2)
            return s;

        else if(s.length()==2)
        {
            if(s.charAt(0)==s.charAt(1))
                s = Character.toString(s.charAt(0));
            return s;
        }

        boolean [] arr = new boolean[26];

        for(int i=0;i<s.length();i++)
        {

            if(arr[s.charAt(i)-'a']==false)
                arr[s.charAt(i)-'a']=true;

            else
            {
                s= ((new StringBuilder(s)).deleteCharAt(i)).toString();
                i--;
            }
        }
        return s;
    }   

    public static void main(String [] args)
    {
        String s = "abbashbhqa";
        System.out.println(duplicate_removal(s));
    }
}

Upvotes: 0

Lior Kogan
Lior Kogan

Reputation: 20688

O(n):

Define an array L[26] of booleans. Set all to FALSE. Construct a new empty string

Walk over the string and for each letter check if L [x] is FALSE. If so, append x to the new string and set L [x] to 1.

Copy new string to the old one.

Upvotes: 3

dev_null
dev_null

Reputation: 1997

as soon as you iterate string you create a set (or hash set). in case the alphabet is limited (English letters as in your example) you just can create a 256 boolean array and use ASCII code as a key to it. Make all booleans to be false at starting point. Each iteration you check if array[] is false or true. In case it's false, the symbol is not a duplicate, so you mark it into array[] = true, do not remove from the string and go on. in case it's true - the symbol is a duplicate

Upvotes: 1

Related Questions