Preface explains

Algorithm learning, daily brush problem record.

Subject to connect

Calculates the length of the longest string with no duplicate characters

The subject content

Given a string, find the longest string that does not contain repeating characters.

Example 1:

Input: s = “abcabCBb”

Output: 3

Explanation: Since the oldest string with no duplicate characters is “ABC”, its length is 3.

Example 2:

Input: s = “BBBBB”

Output: 1.

Explanation: Since the oldest string with no duplicate characters is “b”, its length is 1.

Example 3:

Input: s = “pwwkew”

Output: 3

Explanation: Since the oldest string with no duplicate characters is “wke”, its length is 3.

Note that your answer must be the length of the substring, “pwke” is a subsequence, not a substring.

Example 4:

Input: s = “”

Output: 0

Tip:

0 <= s.length <= 5 * 10^4

S consists of letters, digits, symbols, and Spaces

The analysis process

Method 1:

The first thing that comes to mind is the dumbest way to construct a substring, using a three-level for loop, starting with each character, and then iterating each time to see if the character is repeated. If so, stop, and the substring is constructed. Compare the length of each substring to get the maximum length of the string.

Class Solution {public int lengthOfLongestSubstring(String s) {// lengthOfLongestSubstring size = 0; if (s ! = null && !" ".equals(s) &&s.length () > 0) {List<Character> charList = new ArrayList<>(); For (int n = 0; int n = 0; n <= s.length() - 1; ++n) {for (int I = n; i <= s.length() - 1; ++i) { char c = s.charAt(i); If (I > n) {Boolean isRepeat = false; for (int j = i - 1; j >= n; --j) { if (charList.contains(c)) { isRepeat = true; break; } } if (! isRepeat) { charList.add(c); } else { break; } } else { charList.add(c); }} // Update the maximum string length if (charlist.size () > size) {size = charlist.size (); } // Clear the substring list. Charlist.clear (); } } return size; }}Copy the code

After submitting the code, unfortunately, the message timed out.

So this is not an option.

Method 2:

We to optimize, three layers of the for loop too much, the following optimization into two layers for loop, as well as each character as to construct the substring in the beginning, but each time with a List of the contains method can directly determine whether character repeat, reduce a layer for loop, the last and contrast each child the length of the string is the eldest son string length.

Class Solution {public int lengthOfLongestSubstring(String s) {// lengthOfLongestSubstring = 0; if (s ! = null && !" ".equals(s) &&s.length () > 0) {List<Character> charList = new ArrayList<>(); For (int I = 0; int I = 0; i <= s.length() - 1; ++ I) {for (int j = I; j <= s.length() - 1; ++j) { char c = s.charAt(j); If (charlist.contains (c)) {break; if (charlist.contains (c)) {break; } else { charList.add(c); }} // Update the maximum string length if (charlist.size () > size) {size = charlist.size (); } // Clear the substring list. Charlist.clear (); } } return size; }}Copy the code

After submitting the code, the execution time was 817ms, beating 5.01% of users in time, 38.3MB in memory consumption and 88.51% in space.

You can see that there’s no timeout, but the running time is not very good, it’s close to timeout.

Method 3:

Let’s continue to optimize, two layers of the for loop or too much, the following optimization into a for loop, directly through the results of a string of characters, this time don’t have to List the List to save substring, set to use a Map to store information, traverse the characters when saved to the character and the character of index in the Map, once encounter repeated characters, To prove that the substring is finished, we can recalculate the length of the substring by simply changing the starting index, updating the length of the substring each time, and finally get the maximum length of the substring.

Class Solution {public int lengthOfLongestSubstring(String s) {// lengthOfLongestSubstring = 0; if (s ! = null && !" <Character, Integer> Map = new HashMap<>(); ".equals(s) && s.string () > 0) { Int start = 0; For (int I = 0; i <= s.length() - 1; ++i) { char c = s.charAt(i); If (map.containsKey(c)) {int index = map.get(c) + 1; If (index > start) {start = index; Int length = i-start + 1; int length = i-start + 1; If (length > size) {size = length; } map.put(c, i); } } return size; }}Copy the code

After submitting the code, it took 7ms to execute, beating 79.49% of users in time, 38.7MB in memory consumption and 37.13% in space consumption.

As you can see, the running time has decreased significantly, from 817ms to 7ms.

Summarize the problem solving

I’ve optimized it twice, going from timeouts, optimizing for no timeouts, and then optimizing for significantly lower runtimes, and there are ways to do shorter runtimes, so you’re welcome to point that out.

The original link

The original link: mp.weixin.qq.com/s/59JgZtywH…