The third question of force deduction -- the longest substring without repeated characters

Preface

The day has stopped , You can't stop writing questions every Tuesday ！

This question , It is also moderately difficult , Then I am also a fierce operator , Submit more than fivepercent ~~. I especially want to know who has been surpassed by me

（ Actually, it exceeds 7%）

Here I want to say one more thing first , Do this kind of algorithm problem , There are thousands of ideas , But if there were less algorithms before , May not jump out of the inherent set of business ideas in a short time , Take more turns , Maybe I just stuck myself .

Actually, I feel , Do algorithms , We should throw away the burden of experience , Really use your brain , Use your pen to draw a picture on the paper , Write down , There may be ideas . And brushing algorithm problems can really make our increasingly solidified business thinking more flexible .（ It's just a personal feeling , In fact, I also have a batch of dishes , But every time I solve the problem , No matter more than a few percent , I'm very happy to be able to do it ）

Topic analysis

I'd like to offer you

Links to questions

Then here are the specific topics

Longest substring without repeating characters

Given a string  s , Please find out the length of the longest substring without repeating characters .

Example  1:

Input : s = "abcabcbb"

Output : 3 

explain :  Because the longest substring without repeating characters is  "abc", So its length is  3.

Example  2:

Input : s = "bbbbb"

Output : 1

explain :  Because the longest substring without repeating characters is  "b", So its length is  1.

Example  3:

Input : s = "pwwkew"

Output : 3

explain :  Because the longest substring without repeating characters is  "wke", So its length is  3.

Please note that , Your answer must be   Substring   The length of ,"pwke"  Is a subsequence , Not substring .

Although the content of this question is not long , But the official gave a medium label

It may be because the title is simple , I still rely on my previous experience in projects , I began to solve the problem .

The solution as fierce as a tiger

Take a look at how I did this meal

public static int LengthOfLongestSubstring2(string? s)
{
 if(string.IsNullOrEmpty(s))
 {
 return 0;
 }
 if(s.Length==1)
 {
 return 1;
 }
 char[] chars = s.ToCharArray();
 Hashtable hashtable = new Hashtable();
 int index = 0;
 int maxLen = chars.Length;
 List<int> list = new List<int>();
 while (index < maxLen)
 { 
 hashtable.Clear();
 for (int i = index; i < chars.Length; i++)
 {
 if (hashtable.ContainsKey(chars[i]))
 {
 list.Add(hashtable.Count);
 index++; 
 break;
 }
 hashtable.Add(chars[i], i);
 if (i == chars.Length - 1)
 {
 index++;
 list.Add(hashtable.Count);
 }
 }

 }
 list.Sort((x, y) => -x.CompareTo(y));
 return list[0];
}

Don't look at the operation , Actually, it can pass all official use cases ！

Ideas as follows

• First rule out special circumstances , Empty input and single character

• General characters , Natural division

• Within the specified cycle （ In fact, it is also to shorten the number of cycles step by step ）, utilize hashtable Characteristics of , Store each byte and index value in the hash table

• Each cycle counts the value of the hash table into List in

• At the end of the cycle , Arrangement List, Sort in reverse order of size , The first value is the value required by the topic .

That's how it's written , I think it's a very typical business writing , A hash table is mixed , List two data structures , Obviously, it will consume more memory , That is, spatial complexity . in addition , Go through it many times , It will also increase the time complexity . So this is an experience , Go beyond the direction of problem-solving thinking , A solution of collision , Obviously, it cannot be regarded as a standard , Standard solution ！

Standard solution

I won't say more about the analysis of the solution , Here you are

Portal

as well as C# Solution method , This official has no standard answer , I'm based on Java The writing method of is slightly adjusted and changed to C# Writing

public static int LengthOfLongestSubstring(string? s)
{
 //  Hash set , Record whether each character appears
 HashSet<Char> occ = new HashSet<Char>();
 int n = string.IsNullOrEmpty(s) ? 0 : s.Length;
 //  Right pointer , The initial value is  -1, It's like we're on the left side of the left bound of the string , It's not moving yet
 int rk = -1, ans = 0;
 for (int i = 0; i < n; ++i)
 {
 if (i != 0)
 {
 //  The left pointer moves one space to the right , Remove a character
 occ.Remove(s[i - 1]);
 }
 while (rk + 1 < n && !occ.Contains(s[rk + 1]))
 {
 //  Keep moving the right pointer
 occ.Add(s[rk + 1]);
 ++rk;
 }
 //  The first  i  To  rk  A character is a very long non repeating character substring
 ans = Math.Max(ans, rk - i + 1);
 }
 return ans;

}

Measured or official solution seconds , Just take out 99%+ Record of submission .

Finally, I talked about my experience in doing several algorithm problems .

First of all, I recommend you to brush more questions when you have time , I've been pressing for the project now , Can't finish it , And I'm usually a little lazy , The plan you make for yourself is one question a week , Very low , But every time I try my best to solve the problem in my own way , Then go to see the official conclusion , The previous two questions are like this . Although my method is very rough , But after passing , It brings great comfort to my heart .

in addition , Actually, do algorithm problems , As I started to say , We need to put aside the burden of experience , This is actually an exam question , There must be a standard solution , If you find that your code is written around , Or there are many nested conditions , It's probably going in the wrong direction , Unless there is a specific idea , I think I can do it like this . Just like my problem , I actually write List When , I feel sure the result will not be too good , Even passing is inefficient .

Okay , That's it today , Continue painting next week , After this rush , Brush a few more times a week .