Longest Substring Without Repeat

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

Example

s: “workattech”
Result: 6
Explanation: Longest vaild substring is “workat”.

s: “mississippi”
Result: 3
Explanation: Longest vaild substrings are “mis” and “sip”, both of length 3.

Testing

Input Format

The first line contains an integer ‘T’ denoting the number of test cases.

For each test case, the input has two lines:

• An integer ‘n’ denoting the length of the string.
• The string s.

Output Format

For each test case, the output contains a line with an integer denoting the length of the longest substring in s having distinct characters.

Sample Input

2
10
workattech
11
mississippi

Expected Output

6
3

Constraints

1 <= T <= 10
1 <= n <= 106
The string s consists of lowercase English characters.

import java.util.HashMap;
import java.util.Map;

public class LongestSubString {
    static int longestSubstringWithoutRepeat(String s) {
        int[] chars = new int[128];
        int left = 0, right = 0, res = 0;
        while (right < s.length()) {
            char r = s.charAt(right);
            chars[r]++;
            while (chars[r] > 1) {
                char l = s.charAt(left);
                chars[l]--;
                left++;
            }
            res = Math.max(res, right - left + 1);
            right++;
        }
        return res;
    }

    public static void main(String[] args) {
        String s;
        s = "bbbbb";
        s = "abcabc";
        s = "pwwkew";
        s = "abcabcbb";
        s = "workattech";
        s = "mississippi";
        s = " ";
        s = "au";
        s = "dvdf";
        System.out.println(longestSubstringWithoutRepeat(s));
    }
}

Explanation:

The faster approach would be keeping an array of length 128 (All possible characters) and using the char as index keep the count as 0. Travel from left to right and increase the character count. If the count goes higher than 1 that string is not anymore valid. Adjust the left position and reduce the corresponding character count. Do this till the end of string. Finally return the length between left and right pointers.