Click here to read more about algorithmic interviewing

Topic describes

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

Example 1:

Input: s = “abcabcbb” Output: 3

Explanation: Since the oldest string without repeating characters is “ABC”, its length is 3.

Example 2:

Input: s = “BBBBB” Output: 1

  • Explanation: Since the oldest string without repeating characters is “b”, its length is 1. *

Example 3:

Input: s = “pwwkew” output: 3

Explanation: Since the oldest string without repeating 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 * 104
  • S consists of letters, digits, symbols, and Spaces

Double pointer + hash table solution

Define two Pointers I,j to indicate that the substring being processed is [I,j]. [I,j] always contains no duplicate characters.

Scan from front to back while maintaining a hash table that records the number of occurrences of each character in [I,j].

During the traversal, j increments continuously, and at the same time increments the number of occurrences of the JTH character in the hash table by one.

Get (r) > 1 indicates that the JTH character has appeared before. At this point, the position of I should be updated (to move it right) until map.get(r) > 1 is not satisfied, indicating that [I,j] is restored without repeating characters. Also update the maximum length with the [I,j] length.

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> map = new HashMap<>();
        int ans = 0;
        for (int i = 0, j = 0; j < s.length(); j++) {
            char r = s.charAt(j);
            map.put(r, map.getOrDefault(r, 0) + 1);
            while (map.get(r) > 1) {
                char l = s.charAt(i);
                map.put(l, map.get(l) - 1);
                i++;
            }
            ans = Math.max(ans, j - i + 1);
        }
        returnans; }}Copy the code

Time complexity: Although there are two layers of loops, each character is inserted and deleted in the hash table at most once, and the complexity is O(n)O(n)O(n)

Space complexity: Hash table is used for character recording, complexity is O(n)O(n)O(n)

The last

This is the third article in our “Brush through LeetCode” series. The series started on 2021/01/01. There are 1916 questions in LeetCode as of the start date, some of which have locks.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

As the number of LeetCode questions keeps increasing with weekly and biweekly competitions, in order to facilitate our progress statistics, we will calculate the progress according to the total number of questions at the beginning of the series as the denominator and the completed questions as the numerator. Current progress is 3/1916.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: Github address & Gitee address.

In the repository, you’ll see links to the series, the corresponding code for the series, the LeetCode source links, and some other preferred solutions.


# Algorithms and data structures

# LeetCode antithesis

# Algorithmic interview