Длина самой длинной общей подстроки без повторяющихся символов

Question

Учитывая «abcabcbb», ответ «а», который длина 3.

Учитывая «BBBBB», ответ «б», с длина 1.

Учитывая «pwwkew», ответ «WKE», с длиной 3. следует отметить, что ответ должен быть подстроку, «pwke» подпоследовательность и не подстроки.

Я разработал решение, которое сработало, но не удалось выполнить несколько тестовых примеров. Затем я нашел лучшее решение, и я переписал его, чтобы попытаться понять его. Решение ниже работает безупречно, но примерно через 2 часа борьбы с этой штукой я все еще не понимаю, почему эта конкретная строка кода работает.

import java.util.*; 
import java.math.*; 

public class Solution { 

    public int lengthOfLongestSubstring(String str) { 

    if(str.length() == 0) 
    return 0; 

    HashMap<Character,Integer> map = new HashMap<>(); 
    int startingIndexOfLongestSubstring = 0; 
    int max = 0; 

    for(int i = 0; i < str.length(); i++){ 
     char currentChar = str.charAt(i); 
     if(map.containsKey(currentChar)) 
     startingIndexOfLongestSubstring = Math.max(startingIndexOfLongestSubstring, map.get(currentChar) + 1); 

     map.put(currentChar, i); 
     max = Math.max(max, i - startingIndexOfLongestSubstring + 1); 

     }//End of loop 

    return max; 

    } 
} 

линия в вопросе

max = Math.max(max, i - startingIndexOfLongestSubstring + 1);

Я не понимаю, почему это работает. Мы берем максимум между нашим предыдущим максимумом и разницей между нашим текущим индексом и начальным индексом того, что в настоящее время является самой длинной подстрокой, а затем добавлением 1. Я знаю, что код получает разницу между нашим текущим индексом и startIndexOfSubstring, но я не могу концептуализировать ПОЧЕМУ он работает, чтобы дать нам предполагаемый результат; Может кто-нибудь, пожалуйста, объясните мне этот шаг, особенно ПОЧЕМУ он работает?

Answer 1

Я обычно плохо объясняя, позвольте мне дать ему шанс на рассматривая пример.

Строка "wcabcdeghi".

Забудьте код в течение минуты и предположите, что мы пытаемся придумать логику.

1. Мы начинаем с w и продолжаем идти, пока не достигнем c -> a -> b -> c.
   Нам нужно остановиться в этой точке, потому что «c» повторяется. Поэтому нам нужна карта для хранения, если символ повторяется. (Код:map.put(currentChar, i);)
2. Теперь, когда мы знаем, повторяется ли символ, нам нужно знать, что такое max. до сих пор. (В коде -) max
3. Теперь мы знаем, что нет смысла отслеживать количество первых двух переменных w-> c. Это потому, что, включая это, мы уже получили Max. стоимость. Поэтому, начиная с следующей итерации, нам нужно проверить длину только с a -> b -> в ближайшее время.
   Позволяет иметь переменную (В коде -) startingIndexOfLongestSubstring, чтобы отслеживать это.(Это должно было быть названо startIndexOfNonRepetativeCharacter, то опять же я плохо с именованием).
4. Теперь мы снова продолжаем, но дождаться, что мы до сих пор не доработали, как отслеживать подстроку, которую мы сейчас разбираем. (т. е. от abcd ...)
   Придумывая это, мне нужна только позиция «a» (startingIndexOfNonRepetativeCharacter), чтобы узнать длину текущей подстроки, которую мне нужно сделать есть (В коде -) i - startingIndexOfLongestSubstring + 1 (текущей позиции символа. - не-repetative длина символа + (вычитание не делает включительно с обеих сторон так, добавляющих 1) Назовём эту currentLength
5. Но ждать, что мы будем . делать с этими подсчетами Каждый раз, когда мы находим новую переменные, мы должны проверить, если это может привести к поломке currentLength нашему максимума Так (в коде -). max = Math.max(max, i - startingIndexOfLongestSubstring + 1);
6. сейчас мы рассмотрели большинство утверждений, которые нам нужны, и в соответствии с нашей логикой каждый раз, когда мы сталкиваемся с переменной, которая уже присутствовала, все, что нам нужно, это startingIndexOfLongestSubstring = map.get(currentChar). Так почему мы делаем Max?
   Рассмотрим сценарий, в котором String является «wcabcdewghi». когда мы начинаем обрабатывать наш новый счетчик как a -> b -> c -> d -> e ->w На этом этапе наша логика проверяет, присутствовал ли этот символ ранее или нет. С момента своего появления он начинает отсчет от индекса «1». Который полностью испортил весь счет. Поэтому нам нужно убедиться, что следующий индекс, который мы берем из карты, всегда больше начальной точки нашего счета (т. Е. Выберите символ с карты, только если символ встречается до startingIndexOfLongestSubstring).

Надеюсь, что я ответил на все строки в коде и в основном, если объяснение было понятным.

Answer 2

Поскольку

i - startingIndexOfLongestSubstring + 1 

это количество символов между i и startingIndexOfLongestSubstring индексов. Например, сколько символов между позициями 2 и 3? 3-2=1, но у нас есть 2 символа: на позиции 2 и позиции 3.

Я описал каждое действие в коде:

public class Solution { 

    public int lengthOfLongestSubstring(String str) { 

     if(str.length() == 0) 
      return 0; 

     HashMap<Character,Integer> map = new HashMap<>(); 
     int startingIndexOfLongestSubstring = 0; 
     int max = 0; 

     // loop over all characters in the string 
     for(int i = 0; i < str.length(); i++){ 
      // get character at position i 
      char currentChar = str.charAt(i); 
      // if we already met this character 
      if(map.containsKey(currentChar)) 
       // then get maximum of previous 'startingIndexOfLongestSubstring' and 
       // map.get(currentChar) + 1 (it is last occurrence of the current character in our word before plus 1) 
       // "plus 1" - it is because we should start count from the next character because our current character 
       // is the same 
       startingIndexOfLongestSubstring = Math.max(startingIndexOfLongestSubstring, map.get(currentChar) + 1); 

      // save position of the current character in the map. If map already has some value for current character 
      // then it will override (we don't want to know previous positions of the character) 
      map.put(currentChar, i); 
      // get maximum between 'max' (candidate for return value) and such value for current character 
      max = Math.max(max, i - startingIndexOfLongestSubstring + 1); 

     }//End of loop 

     return max; 

    } 
}