Shulou(Shulou.com)06/01 Report--

This article mainly introduces how to view the longest substring of non-repetitive characters in leetcode, which has a certain reference value, and interested friends can refer to it. I hope you can learn a lot after reading this article.

Topic link

Https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/

Topic description

Given a string, please find out the length of the longest substring that does not contain repeating characters.

Example 1:

Input: "abcabcbb" output: 3 explanation: because the longest substring without repeating characters is "abc", its length is 3.

Example 2:

Input: "bbbbb" output: 1 explanation: because the longest substring without repeating characters is "b", its length is 1.

Example 3:

Input: "pwwkew" output: 3 explanation: because the longest substring without repeating characters is "wke", its length is 3. Please note that your answer must be the length of the substring. "pwke" is a subsequence, not a substring. The idea of solving the problem

Tags: sliding window

The time complexity of the violent solution is high, which will reach O (n ^ 2), so the sliding window method is adopted to reduce the time complexity.

Define a map data structure store (kjournal v), where the key value is a character, and the value value is a character position + 1, plus 1 means that it is not repeated until after the character position.

We define the start position of the unrepeated substring as start and the end position as end.

As end keeps traversing backwards, it will encounter the same situation as the characters in the [start, end] interval. At this time, the character is used as the key value, the value value is obtained, and the start is updated. There are no duplicate characters in the [start, end] interval.

Whether or not the start is updated, its map data structure and the resulting ans are updated.

Time complexity: O (n)

Code class Solution {public int lengthOfLongestSubstring (String s) {int n = s.length (), ans = 0; Map map = new HashMap (); for (int end = 0, start = 0; end

< n; end++) { char alpha = s.charAt(end); if (map.containsKey(alpha)) { start = Math.max(map.get(alpha), start); } ans = Math.max(ans, end - start + 1); map.put(s.charAt(end), end + 1); } return ans; }}画解

Thank you for reading this article carefully. I hope the article "how to check the longest substring without repeating characters in leetcode" shared by the editor will be helpful to you. At the same time, I also hope you will support us and pay attention to the industry information channel. More related knowledge is waiting for you to learn!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.