Вопрос:

Ссылка: 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 состоит из английских букв, цифр, символов и пробелов.

Решение:

Подход: Здесь мы проверяем каждую подстроку на наличие в ней самого длинного неповторяющегося символа.

  1. Метод lengthOfLongestSubstring принимает на вход строку s и возвращает целое число, представляющее длину самой длинной подстроки без повторяющихся символов.
  2. Он инициализирует переменную ans для хранения максимальной длины найденной подстроки. Он начинается с ans, установленного на 0.
  3. Код использует цикл for для перебора каждого символа во входной строке s. Переменная цикла i представляет начальный индекс подстроки.
  4. Внутри цикла создается временный список temp для хранения символов текущей рассматриваемой подстроки. Переменная t используется для отслеживания длины текущей подстроки.
  5. Другой цикл for-each используется для перебора символов подстроки, начиная с индекса i. Он преобразует подстроку в массив символов, используя toCharArray().
  6. Для каждого символа c в подстроке проверяется, содержит ли уже этот символ temp. Если это так, это означает, что подстрока содержит повторяющиеся символы, и внутренний цикл завершается с помощью break.
  7. Если символ c еще не присутствует в temp, он добавляется в список, а длина t увеличивается.
  8. После завершения внутреннего цикла максимальная длина ans обновляется с помощью Math.max(ans, t) для отслеживания самой длинной найденной подстроки.
  9. Наконец, после того как внешний цикл завершает итерацию по всем возможным начальным индексам, длина самой длинной подстроки без повторяющихся символов возвращается как 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)

Заключение:

Надеюсь, что этот блог поможет вам решить вопрос, а также развеет ваши сомнения относительно решения. Пожалуйста, прокомментируйте, если вы знаете какие-либо новые подходы. Если у вас есть какие-либо сомнения, пожалуйста, прокомментируйте, и мы обсудим их.

Удачного кодирования.