The subject content

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

Input:"abcabcbb"Explanation: Because the oldest string without repeating characters is"abc"So its length is 3.Copy the code

Example 2:

Input:"bbbbb"Explanation: Because the oldest string without repeating characters is"b"So its length is 1.Copy the code

Example 3:

Input:"pwwkew"Explanation: Because the oldest string without repeating characters is"wke"So its length is 3. Please note that your answer must be the length of the substring,"pwke"It's a subsequence, not a substring.Copy the code

Their thinking

My own problem solving ideas described here are indeed stupid to death, but they are also summed up by myself through the analysis of the nature of the problem. For the moment, I will record that after I have my own problem solving ideas, I will learn other people’s more excellent problem solving ideas, which is quite great for my improvement.

See figure:

char curchar; // Records the characters currently read
String curMaxStr; // Record the longest string that has no repeat
int curMaxLen; // Record the length of the last longest unrepeated string
String totalMaxStr; // Record the longest unrepeated string
int totalMaxLen; // Record the total length of the longest non-repeating string
Copy the code

Here are my thoughts on the question:

1. For loop over the string, usingcurCharRecord the characters currently read;
2. judgecurMaxStrThere is no such character incurCharIf not, concatenate the character tocurMaxStrAnd will becurMaxLenPlus 1, ifcurMaxLenGreater than or equal tototalMaxLen, it willcurMaxStrandcurMaxLenAssigned tototalMaxStrandtotalMaxLen.
3. ifcurMaxStrThere’s this charactercurChar, so from the current position forward reverse order traversal, must be able to find the position of the repeated character, will repeat the character to the currentcurCharPosition of the string assigned tocurMaxStrIf thecurMaxLenGreater than or equal tototalMaxLen, it willcurMaxStrandcurMaxLenAssigned tototalMaxStrandtotalMaxLen.

Specific code

public static int lengthOfLongestSubstring(String s) {
        // When the length of string s is 0, there is no oldest string
        char curChar;
        String curMaxStr = "", totalMaxStr = "";
        int curMaxLen = 0, totalMaxLen = 0;
		if(s.length() == 0) {
            totalMaxLen = 0;
        }
        for(int i = 0; i < s.length(); i++) {
            curChar = s.charAt(i);
            // The current character does not duplicate the characters in the current longest string
            if(! curMaxStr.contains(String.valueOf(curChar))) {// Concatenates the current character to the current longest string
				curMaxStr += curChar;
				The current maximum length is +1
				curMaxLen ++;
				if (curMaxLen >= totalMaxLen) {
					totalMaxStr = curMaxStr;
					totalMaxLen = curMaxLen;
				}
				//System.out.println("++++curChar:" + curChar + " curMaxStr:" + curMaxStr + " curMaxLen:" + curMaxLen + " totalMaxStr:" + totalMaxStr + " totalMaxLen:" + totalMaxLen);
			}
            else {
            	// Record the position of the repeat point
				int repeatPos = i;
				curMaxStr = String.valueOf(curChar);
				curMaxLen = 1;
				// I does not traverse to the beginning, and the character moving forward from the repeated position is not repeated with the repeated character
				while(i > 0 && s.charAt(i - 1) != curChar) {
					curMaxStr = s.charAt(--i) + curMaxStr;
					curMaxLen++;
					//System.out.println("----curChar:" + curChar + " curMaxStr:" + curMaxStr + " curMaxLen:" + curMaxLen + " totalMaxStr:" + totalMaxStr + " totalMaxLen:" + totalMaxLen);
					if(curMaxLen >= totalMaxLen) { totalMaxStr = curMaxStr; totalMaxLen = curMaxLen; } } i = repeatPos; }}return totalMaxLen;
    }
Copy the code

Here’s what I saw in the comments after I solved the problem. It was great, and I’m sharing it here. If you think my idea is too stupid, check out this code:

public static int lengthOfLongestSubstring(String s) {
        int maxLength = 0;
        String str = "";
        for (int i = 0; i < s.length(); i++) {
			int index = str.indexOf(s.charAt(i));
			str = str + s.charAt(i);
			// There is a repetition
			if(index >= 0) {
				str = str.substring(index + 1);
			} else {
				if(str.length() > maxLength) { maxLength = str.length(); }}}return maxLength;

    }
Copy the code