Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

The title

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

Train of thought

Reocord (int[]); reocord (int[]); Record [CHars [I]] == -1// indicates that this character did not appear before only need to put the I position of the character to dp[I-1] situation above II. record[chars[i-1] ! Chars [I] = chars[I] = chars[I] Record [I] =record[I] =record[I] =record[I] =record[I] =record[I] =record[I] =record[I] =record[I]Copy the code

code

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() == 0) return 0;

        char[] chars = s.toCharArray();
        int[] record = new int[256];
        int[] dp = new int[chars.length];
        int max = 1;
        Arrays.fill(record, -1);
        dp[0] = 1; // represents a string ending with the character above position 0
        record[chars[0]] = 0;
        for (int i = 1; i < chars.length; i++) {
            if(record[chars[i]] ! = -1) { // indicates that the character is preceded
                // see if this character is included in the range 0123456
                if (i - record[chars[i]] > dp[i - 1]) { // The description is not in the scope
                    dp[i] = dp[i - 1] + 1;
                    max = Math.max(dp[i], max);
                    record[chars[i]] = i;

                } else {  // Specify the scopedp[i] = i - record[chars[i]]; max = Math.max(dp[i], max); record[chars[i]] = i; }}else { // This character does not appear before, so it can be added directly
                dp[i] = dp[i - 1] + 1; max = Math.max(dp[i], max); record[chars[i]] = i; }}returnmax; }}Copy the code