Вопрос:
Ссылка: https://leetcode.com/problems/длинная-подстрока-без-повторяющихся-символов/
Имея строку s
, найдите длину самого длинного
подстрока
без повторяющихся символов.
Пример 1:
Input: s = "abcabcbb" Output: 3 Explanation: The answer is "abc", with the length of 3.
Пример 2:
Input: s = "bbbbb" Output: 1 Explanation: The answer is "b", with the length of 1.
Пример 3:
Input: s = "pwwkew" Output: 3 Explanation: The answer is "wke", with the length of 3. Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.
Ограничения:
0 <= s.length <= 5 * 104
s
состоит из английских букв, цифр, символов и пробелов.
Решение:
Подход: Здесь мы проверяем каждую подстроку на наличие в ней самого длинного неповторяющегося символа.
- Метод
lengthOfLongestSubstring
принимает на вход строкуs
и возвращает целое число, представляющее длину самой длинной подстроки без повторяющихся символов. - Он инициализирует переменную
ans
для хранения максимальной длины найденной подстроки. Он начинается сans
, установленного на 0. - Код использует цикл for для перебора каждого символа во входной строке
s
. Переменная циклаi
представляет начальный индекс подстроки. - Внутри цикла создается временный список
temp
для хранения символов текущей рассматриваемой подстроки. Переменнаяt
используется для отслеживания длины текущей подстроки. - Другой цикл for-each используется для перебора символов подстроки, начиная с индекса
i
. Он преобразует подстроку в массив символов, используяtoCharArray()
. - Для каждого символа
c
в подстроке проверяется, содержит ли уже этот символtemp
. Если это так, это означает, что подстрока содержит повторяющиеся символы, и внутренний цикл завершается с помощьюbreak
. - Если символ
c
еще не присутствует вtemp
, он добавляется в список, а длинаt
увеличивается. - После завершения внутреннего цикла максимальная длина
ans
обновляется с помощьюMath.max(ans, t)
для отслеживания самой длинной найденной подстроки. - Наконец, после того как внешний цикл завершает итерацию по всем возможным начальным индексам, длина самой длинной подстроки без повторяющихся символов возвращается как
ans
.
class Solution { public int lengthOfLongestSubstring(String s) { int ans=0; for(int i=0; i<s.length(); i++){ List<Character> temp = new ArrayList<>(); int t=0; for(char c : s.substring(i).toCharArray()){ if(temp.contains(c)){ break; } temp.add(c); t++; } ans = Math.max(ans, t); } return ans; } }
Временная сложность: O(N²)
Космическая сложность: O(N)
Заключение:
Надеюсь, что этот блог поможет вам решить вопрос, а также развеет ваши сомнения относительно решения. Пожалуйста, прокомментируйте, если вы знаете какие-либо новые подходы. Если у вас есть какие-либо сомнения, пожалуйста, прокомментируйте, и мы обсудим их.
Удачного кодирования.