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

Editor to share with you how to achieve the longest substring of non-repetitive characters in the programming language, I believe most people do not know much about it, so share this article for your reference. I hope you will learn a lot after reading this article. Let's learn about it!

Title:

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.

Ideas for solving the problem:

Brute force solution, the time complexity is O (n ^ 3), because to traverse all characters, traverse substrings to confirm whether there are duplicate characters, pass

Slide window, maintain a sliding window with index [iMagnej), update sliding window directly for existing characters I', you need to retain each character value and its index, that is, by character mapping index position hash mapping: Key is character value, Value is index position character mapping: ASCII code total 128characters, maintain an integer array of 128length The array index value maps 128 characters, and the storage element value is the character position.

Hash mapping:

Java:

Class Solution {public int lengthOfLongestSubstring (String s) {char [] chars = s.toCharArray (); / / convert to character array if (chars.length = = 0) return 0; HashMap map = new HashMap (); / / establish hash mapping int size = s.length (), count = 0, I = 0; for (int j = 0; j)

< size; j++) {//遍历字符 if (map.containsKey(chars[j]))//如果映射中存在该字符 i = Math.max(map.get(chars[j]), i);//更新滑动窗口的左边界 i count = Math.max(count, j - i);//更新 count 为最大值 map.put(chars[j], j + 1);//更新映射中该字符映射的 Value 值为当前位置加一 } return count + 1;//返回最大累加总数, 需要加 1 }} Python: class Solution: def lengthOfLongestSubstring(self, s: str) ->

Int: if not s: return 0 hash_map = dict () # set up the dictionary size = len (s) I, count = 0,0 for j, c in enumerate (s): # enumeration character if c in hash_map: # if the character I = max (I) exists in the map Hash_ Maps [c]) # Update the left boundary of the sliding window I count = max (count, Jmuri) # Update count to the maximum value hash_ Maps [c] = jambo1 # the Value value of this character map in the update map returns the maximum cumulative total for the current position plus one return count+1 #, which needs to be added by 1

Character mapping:

Java:

Class Solution {public int lengthOfLongestSubstring (String s) {char [] chars = s.toCharArray (); if (chars.length = = 0) return 0; int [] index = new int [128]; / / establish a 128-bit ASCII character mapping table int size = s.length (), count = 0, I = 0; for (int j = 0; j)

< size; j++) {//遍历字符 i = Math.max(index[chars[j]], i);//更新滑动窗口的左边界 i count = Math.max(count, j - i);//更新 count 为最大值 index[chars[j]] = j + 1;//更新映射中该字符所在元素值为当前位置加一 } return count + 1;//返回最大累加总数, 需要加 1 }} Python: class Solution: def lengthOfLongestSubstring(self, s: str) ->

Int: if not s: return 0 size = len (s) I, count = 0,0 index = [0] * 128# create an ASCII code character mapping table for j, c in enumerate (s): # enumerated characters I = max (I, index [c)] # Update the left boundary of the sliding window I count = max (count) Jmuri) # Update count to the maximum value index [ord (c)] = job1 # Update the element value of the character in the update mapping to the current position plus a return count+1 # returns the maximum cumulative total, which needs to be added by 1.

Because Python has no concept of characters, you need to convert the ord () function to ASCII numbers.

These are all the contents of the article "how to achieve the longest substring without repeating characters in a programming language". Thank you for reading! I believe we all have a certain understanding, hope to share the content to help you, if you want to learn more knowledge, welcome to follow the industry information channel!

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.