Longest substring without repeating characters

Problem

A tracking code is a string. Find the length of its longest substring (a block of consecutive characters) in which no character appears twice.

Input: One line with the string (no spaces).
Output: One number: the length of the longest such substring.
Constraints: 1 ≤ length ≤ 100000
Letters and digits; capital and small letters are different

Example 1

Input

abcabcbb

Output

The longest block without a repeat is abc, length 3.

Example 2

Input

pwwkew

Output

wke has length 3; pwwke is not allowed because w repeats.

Try the problem first. Open one hint at a time.

Hint 1

Keep a window [start, i] with no repeats, and a map from each character to the last position where it was seen.

Hint 2

When the current character was seen at a position >= start, move start to that position + 1.

Hint 3

Update the best length after every step: i - start + 1. Never move start backwards.

Write your Java code, run it on the examples and submit it to hidden tests.