Алгоритм для удаления повторяющихся символов из строки

Question

Возьмем строку «abbashbhqa». Мы должны удалить дубликаты символов таким образом, чтобы выход был «abshq». Одним из возможных решений является проверка каждого символа с другими присутствующими в строке и последующим манипулированием. Но для этого требуется сложность времени O (n^2). Есть ли оптимизированный подход для этого?

Answer 1

O (N):

определить массив L [26] из Булев. Установите для всех значение ЛОЖЬ. Построить новую пустую строку

Пройдите по строке и для каждой буквы проверьте, является ли L [x] ЛОЖНЫМ. Если это так, добавьте x в новую строку и установите L [x] равным 1.

Скопируйте новую строку в старую.

Answer 2

как только вы повторяете строку, вы создаете набор (или набор хэшей). в случае, если алфавит ограничен (английские буквы, как в вашем примере), вы можете создать 256 булевых массивов и использовать ASCII-код в качестве ключа к нему. Сделать все булевы ложными в начальной точке. На каждой итерации вы проверяете, является ли массив [] ложным или истинным. Если это неверно, символ не является дубликатом, поэтому вы помещаете его в массив [] = true, не удаляете из строки и продолжаете. в случае, если это правда - это символ дубликат

Answer 3

Вероятно, это будет реализация вышеуказанной проблемы

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)); 
    } 
} 

Answer 4

Я решения с помощью Python и работает в O (N) времени и O (N) пространства - Я использую множество() как установлено, не допускает дубликатов --- В этом случае изменяется порядок элементов - Если вы хотите, чтобы заказ оставался таким же, вы можете использовать OrderedDict(), а также работает в O (n) времени -

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)