Description
Given a string s, find the length of the longest substring without repeating characters.
Tests
As always, let’s start out with the tests:
/// The answer is 'abc', with the length of 3.
///
test 'Example 1';
begin
AssertEqual(3, LongestSubstring('abcabcbb'));
end
/// The answer is 'b', with the length of 1.
///
test 'Example 2';
begin
AssertEqual(1, LongestSubstring('bbbbb'));
end
/// The answer is 'wke', with the length of 3. Notice that
/// the answer must be a substring, 'pwke' is a subsequence
/// and not a substring.
///
test 'Example 3';
begin
AssertEqual(3, LongestSubstring('pwwkew'));
end
Solution
This is a medium level LeetCode question. Coding it is simple if you know the concept of the “sliding window.”
function LongestSubstring(S : String) : Integer;
var
Start, Finish, TheMax : Integer := 0;
TheSet : Set := Set();
begin
while Finish < Length(S) do
begin
if Not TheSet.Contains(S[Finish]) then
begin
TheSet.Add(S[Finish]);
Finish := Finish + 1;
TheMax := Max(TheSet.Length, TheMax);
end
else
begin
TheSet.Remove(S[Start]);
Start := Start + 1;
end
end
Exit TheMax;
end
Use a Set to keep track of the unique characters. Start out with the “window” start and finish at the beginning of the String, and loop until the finish is at the end of the String. If the character at the end of the window is not in the Set, add it and move the end by one. If not, remove the character at the start of the window from the Set and move the start by one.
When the end of the window is at the end of window, return the largest number of characters the Set contained. (Every time you add a character, set the max to the length of the Set, if it is larger than the previous max.
Leave a Reply