Day 67: The oldest string without repeating characters

Make writing a habit together! This is my first day to participate in the “Gold Digging Day New Plan · April More text challenge”, click to see the details of the activity.

I. Problem description

Given a string s, find the length of the smallest string that does not contain repeating characters.

Title link: the oldest string without repeating characters.

Two, the title requirements

Sample 1

Input: s = "abcabcbb" Output: 3 Explanation: Since the oldest string without repeating characters is "ABC", its length is 3.Copy the code

The sample 2

Input: s = "BBBBB" Output: 1 Explanation: Since the oldest string without repeating characters is "b", its length is 1.Copy the code

inspection

1. String, sliding window 2. The recommended time is 20 to 35 minutesCopy the code

Third, problem analysis

Take example 1 as an example. My initial thought was:

Iterating through the string one by one, looking back for the largest substring with the current character as the first digit.

A ABC b bca c CAB 4 a ABC...... And then the last one, b, BCopy the code

My initial idea was hash table (C++ map count), if the current character does not appear in the hash table, then the string length +1, the character hash table +1. Step by step, follow the steps above.

But this algorithm is also very inefficient, so let’s optimize it.

In fact, we can simplify the original two-layer loop to one layer, with L and R as double Pointers to the first character, traversing backwards.

If r does not appear, add the index after it to the hash table, l unchanged, r++.

If r points to a character, l must be one bit after the last character to ensure that there are no duplicate characters in [L,r].

You can follow the pictures on the buckle to help you understand.

Four, coding implementation

1. Before optimization

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
    int i,j,n=s.size(),ans=0,k=0;// Initialize the code
    map<char.int>m;// Hash table storage
    for(i=0; i<n; i++)// Each character is the starting point
    {
        m.clear(a);/ / to empty
        ans=0;//
        for(j=i; j<n; j++)// Look backwards for no repeating characters
        {
            if(m[s[j]]==0)/ / found
            {
                ans++;/ / count
                m[s[j]]++;/ / tag
            }
            else// Exit if not found
                break;
        }
        k=max(k,ans);// Find the maximum value
    }
    return k;// Output the result}};Copy the code

2. After the optimization

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int l,r,n=s.size(),ans=0;// Initialize variables
        map<char.int>m;/ / a hash table
        for(l=0,r=0; r<n; r++)// Interval move
        {
            if(m[s[r]]>0)// The current character conflicts with the hash table
                l=max(l,m[s[r]]);/ / l shift
            m[s[r]]=r+1;// The hash table stores the last bit of the subscript
            ans=max(ans,r-l+1);// Find the maximum value
        }
        return ans;// Output the result}};Copy the code

V. Test results

From 964ms->12ms, no optimization, satisfied.