Hello everyone, I am a programming bear, today is the third day of LeetCode’s daily problem, learning LeetCode’s third problem, “The oldest string without repeating characters”.

The question

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

The sample

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

Answer key

Looking at the sample, we can see that enumerating the starting position of the substring incrementatively, then the legal end must be incrementing, because the starting position i-1, assuming it does not contain the farthest right position j of repeating characters; So for the substring starting position I, since [i-1, j] does not contain repeating characters, its farthest right position which does not contain repeating characters must be greater than or equal to I, so we consider using a sliding window to solve the problem.

In essence, the sliding window takes advantage of the realization of the double pointer and the monotony of pointer movement to constantly move to find the legal interval, which contains the longest interval.

In this case, we can fix the right pointer and find the farthest left pointer that does not contain repeating characters.

In terms of code implementation, we can use queue to simulate double Pointers and assist array CNT to count The Times of each character appearing in the window to determine whether there are repeated characters in the window.

Time complexity: O(n)O(n)O(n)

Space complexity: O(n)O(n)O(n)

Summary: Sliding Windows

C + + code

class Solution {
public:
    queue<char> q;
    int lengthOfLongestSubstring(string s) {
        vector<char> cnt(128.0);
        int ans = 0;
        for (int i = 0; i < int(s.size()); i++) {
            q.push(s[i]), cnt[s[i]]++;
            while (cnt[s[i]] > 1) {
                char frontC = q.front(a); q.pop(a); cnt[frontC]--; } ans =max(ans, int(q.size()));
        }
        returnans; }};Copy the code

Java code

class Solution {
    public int lengthOfLongestSubstring(String s) {
        char[] cnt = new char[128];
        LinkedList<Character> q = new LinkedList<Character>();
        int ans = 0;
        for (int i = 0; i < s.length(); i++) {
            q.add(s.charAt(i));
            cnt[s.charAt(i)]++;
            while (cnt[s.charAt(i)] > 1) {
                char frontC = q.pollFirst();
                cnt[frontC]--;
            }
            ans = Math.max(ans, q.size());
        }
        returnans; }}Copy the code

Title link: https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/

I am a programming bear, continue to output LeetCode problem solving, dACHang interview, Dachang rely on proper point-to-point extrapolation related content, follow ‘a programming bear’, get information.

Welcome to “follow”, “like”, “forward” support ~