0003._Longest_Substring_Without_Repeating_Characters.md

3. Longest Substring Without Repeating Characters

难度: Medium

刷题内容

原题连接

• https://leetcode.com/problems/longest-substring-without-repeating-characters

内容描述

Given a string, find the length of the longest substring without repeating characters.

Example 1:

Input: "abcabcbb"
Output: 3 
Explanation: The answer is "abc", with the length of 3. 
Example 2:

Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.
Example 3:

Input: "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3. 
             Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

解题方案

思路 1 - 时间复杂度: O(N)- 空间复杂度: O(1)******

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int stIdx = 0, maxLen = 0;
        int arr[] = new int[128];
        for(int i=0;i<s.length();i++){
            stIdx = Math.max(arr[s.charAt(i)],stIdx);
            maxLen = Math.max(maxLen, i-stIdx+1);
            arr[s.charAt(i)] = i+1;
        }
        return maxLen;
    }
}