LeetCode-003- The oldest string without repeating characters

The oldest string without repeating characters

Given a string, find the length of the longest string that does not contain repeated characters.

Examples can be found on the LeetCode website.

Source: LeetCode link: leetcode-cn.com/problems/lo… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

Solution one: sliding window method

Starting from the first character, has a record of a pointer p don’t repeat the first character, and then in turn backward traversal, has appeared in the List of characters, to determine whether, if, is calculating the difference between the current position and the position of p pointer, the current is repeated in the length of the substring, and contrast the longest count, if more than the count, Then we move the p pointer one bit to the right and continue iterating back until we know the last character, returning count as the length of the oldest string.

import java.util.ArrayList;
import java.util.List;

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

        int count = 0;
        int charAt = 0;
        List<Character> charList = new ArrayList<Character>(s.length());
        for (int i = 0; i < s.length(); i++) {
            List<Character> subList = charList.subList(charAt, i);
            if (subList.contains(s.charAt(i))) {
                charAt = charList.lastIndexOf(s.charAt(i)) + 1;
            }
            if (i + 1 - charAt > count) {
                count = i + 1 - charAt;
            }
            charList.add(s.charAt(i));
        }
        return count;
    }

    public static void main(String[] args) {
        System.out.println(lengthOfLongestSubstring("abcabcbb")); }}Copy the code