самая длинная подстрока, предел превышен java

Question

С учетом строки найдите длину самой длинной подстроки без повторяющихся символов. Например, самые длинные подстроки без повторения букв для «abcabcbb» являются «ABC», которой длина равна 3. Для «BBBBB» длинная подстрока «б», с длиной 1.

public static int lengthOfLongestSubstring(String s) { 
    if (s.length()==0) 
     return 0; 
    int maxlen = 1; 

    HashMap<Character, ArrayList<Integer>> check = new HashMap<Character,ArrayList<Integer>>(); 
    for (int i = 0; i < s.length(); i++) { 
     for (int j = i; j < s.length(); j++) { 
      if (!check.containsKey(s.charAt(j))) { 
       ArrayList<Integer> value= new ArrayList<>(); 
       value.add(j); 
       check.put(s.charAt(j), value); 
      } 
      else { 
       maxlen = Math.max(j - i, maxlen); 
       ArrayList<Integer> temp = check.get(s.charAt(j)); 
       i=temp.get(temp.size()-1); 
       // get the last index(biggest index) of the key value 
       check.clear(); 
       break; 
      } 
      if(j==s.length()-1) { 
       maxlen = Math.max(j - i + 1, maxlen); 
      } 

     } 
    } 
    return maxlen; 
    } 
} 

Для последний тест длинной повторяемой строки, превышен лимит времени. Не знаю, как оптимизировать. ищут улучшения, спасибо

Answer 1

Вот довольно простое решение, которое должно быть более быстрым, что ваше решение:

public static int longestNonRepeating(final String s) { 
    final Set<Character> unique = new HashSet<>(); 
    int max = 0; 
    for (int i = 0; i < s.length(); ++i) { 
     final char c = s.charAt(i); 
     if (!unique.add(c)) { 
      for (int j = i - unique.size(); j < i; ++j) { 
       if (s.charAt(j) != c) { 
        unique.remove(s.charAt(j)); 
       } else { 
        break; 
       } 
      } 
     } 
     max = Math.max(max, unique.size()); 
    } 
    return max; 
} 

Как это работает?

Мы ходим по String и добавляем символы в Set. Если добавляемый символ уже содержится в Set, то мы знаем, что у нас есть дубликат в текущей подстроке.

В этом случае, начиная с начала текущей подстроки (которая должна быть такой же длины, как размер unique), мы идем. Если мы найдем символ, который не является дубликатом, мы обнаружили, что дубликат должен быть продолжен, мы продолжаем поиск. Как только мы найдем дубликат, мы можем остановить поиск.

Для рода визуализации процесса:

a b c a b c 
0 1 2 3 4 5 
^ 
| 
i 

мы имеем a в нашем уникальном Set.

a b c a b c 
0 1 2 3 4 5 
^
    | 
    i 

a,b мы имеем в нашем уникальном Set.

a b c a b c 
0 1 2 3 4 5 
    ^
     | 
     i 

мы имеем a,b,c в нашем уникальном Set.

a b c a b c 
0 1 2 3 4 5 
^  ^
|  | 
j  i 

Мы стараемся adda к уникальной Set, это дубликат. С самого начала уникальной подстроки попробуйте найти a. К счастью, это 0, нам не нужно ничего удалять из уникального.

a b c a b c 
0 1 2 3 4 5 
^ ^
    |  | 
    j  i 

Мы стараемся addb к уникальной Set, это дубликат. С самого начала уникальной подстроки попробуйте найти b. К счастью, это 1, нам не нужно ничего удалять из уникального.

a b c a b c 
0 1 2 3 4 5 
    ^ ^
     |  | 
     j  i 

Мы стараемся addc к уникальной Set, это дубликат. С самого начала уникальной подстроки попробуйте найти c. К счастью, это 1, нам не нужно ничего удалять из уникального.

И все готово. Самая длинная уникальная подстрока - 3.

Answer 2

Эта проблема может быть решена в O (N), где N - длина строки.

Алгоритм:

1) перебирать символы строки. Следите за последним появлением каждого символа. В каждом магазине букв, как далеко, был предыдущий один и тот же символ. E. g .: Имея строку «abccdae», мы получим список [1, 2, 3, 1, 5, 5, 7]. Обратите внимание, что если символ не произошел до того, как мы установим его в длину до начала слова.

2) Позволяет вызвать этот список, который мы получили V (в примере V = [1, 2, 3, 1, 5, 5, 7]).

3) Определите функцию f (x), которая вычисляет самое длинное слово без повторяющегося символа, который заканчивается с индексом x.

Это справедливо, что: F (0) = 0 F (X) = мин (Р (х-1) + 1, В [х]), х> 0

4) Итерации над словом и вычислить f для каждого индекса.

5) Найдите максимум f.

Каждый шаг - O (N), но если вы играете, вы можете делать все одновременно, улучшая даже постоянный.

Надеюсь, это поможет.

Answer 3

Найдите ниже оптимизированную версию. Усиление по сравнению с первоначальной версией:

• это не создает дополнительные объекты
• не дублировать любой символ, он работает на самой строки данных
• уменьшает количество сравнения шаги

edit2 Загрузите контрольный образец JMH here, который сравнивает алгоритмы из трех ответов на этот вопрос. Прямая ссылка на benchmark result.

public static void main(String[] args) { 
    String[] strings = {"abcabcdebb", "abcbacde", "abb", "bba", 
     "cbaabc", "abccba", "xabccba", "abcxcba", "abccbax", 
     "", "a", "aa", "ab" 
    }; 
    for (String s : strings) { 
     System.out.printf("string: %-10s maxSubStringLength: %d%n", s, 
      maxSubStringLength(s)); 
    } 
} 

static int maxSubStringLength(String string) { 
    if (string.isEmpty()) { 
     return 0; 
    } 
    int maxLength = 1; 
    int low = 0; 
    for (int high = 1; high < string.length(); high++) { 
     for (int pos = high - 1; pos >= low; pos--) { 
      if (string.charAt(pos) == string.charAt(high)) { 
       low = pos + 1; 
       break; 
      } 
     } 
     maxLength = Math.max(maxLength, high - low + 1); 
     if (string.length() - low <= maxLength) { 
      break; 
     } 
    } 
    return maxLength; 
} 

, как это работает

• мы сохраняем указатель на самый левый символ low
• мы увеличиваем указатель правого символа high до максимума на длине строки
• если мы увеличили указатель high, мы ищем назад, если самый правый символ (тот, который находится в позиции high) происходит в подстроках из индекса low до high
• , если это не происходит
  • мы обновляем или поддерживать максимальную длину, в зависимости, если текущие выбранные подстроки больше, чем предыдущая найден максимальной длина
• еще
  • мы перемещаем указатель левого символа в позиции после левой встречаемости
• , если оставшаяся длина подстроки в тест не больше, то максимальная длина, мы можем остановить проверку уже на этом этапе
• продолжает со второй точкой пули

начального постом, чтобы увидеть эволюцию коды

весьма прагматическое решение может быть

public static void main(String[] args) { 
    String s = "abcabcbb"; 
    int maxLength = 1; 
    for (int i = 0; i < s.length(); i++) { 
     for (int j = i+2; j <= s.length(); j++) { 
      String substring = s.substring(i, j); 
      if (hasNoDupeChars(substring) && substring.length() > maxLength) { 
       System.out.println("substring = " + substring); 
       maxLength = substring.length(); 
      } 
     } 
    } 
    System.out.println("maxLength = " + maxLength); 
} 

private static boolean hasNoDupeChars(String substring) { 
    Set<Character> chars = new HashSet<>(); 
    for (Character c : substring.toCharArray()) { 
     if (!chars.add(c)) { 
      return false; 
     } 
    } 
    return true; 
} 

редактировать Как отметил Борис там до сих пор оп возможно. Я не буду этого делать после Дональда Кнут: «Преждевременная оптимизация - это корень всего зла». ;-)

Answer 4

Решение проблемы с временной сложностью O(n). Скорее всего, это будет быстрее, чем другие решения по двум причинам.

1. Это только сравнивает длину цепочки различных последовательных символов с текущим максимумом, когда цепь нарушена, или когда конец String достигается.

2. Отслеживая последний индекс каждого символа, а не набор символов в подстроке, никогда не было никаких причин для удалять любые элементы. Это, конечно, означает, что он использует много памяти, если String имеет много разных символов.

   public static int subStringLength(final String s) { 
       final Map<Character, Integer> indices = new HashMap<>(); 
       int max = 0; 
       int start = 0; 
       final int length = s.length(); 
       for (int i = 0; i < length; i++) { 
        Integer k = indices.put(s.charAt(i), i); 
        if (k != null && k >= start) { 
         max = Math.max(max, i - start); 
         start = k + 1; 
        } 
       } 
       return Math.max(max, length - start); 
   }