longest_substring_without_repeating_characters.cpp File Reference

Solution for Longest Substring Without Repeating Characters problem. More...

#include <iostream>
#include <unordered_map>
#include <deque>
#include <string>
#include <cassert>

Include dependency graph for longest_substring_without_repeating_characters.cpp:

Go to the source code of this file.

Classes
class	Longest_Substring
	Class that solves the Longest Substring Without Repeating Characters problem. More...

Functions
static void	tests ()
	Self-test implementations.
int	main ()
	Main function.

Detailed Description

Solution for Longest Substring Without Repeating Characters problem.

Problem link: https://leetcode.com/problems/longest-substring-without-repeating-characters/description/

Intuition: 1) The intuition is straightforward and simple. We track the frequency of characters. 2) Since we can't use a string to track the longest substring without repeating characters efficiently (as removing a character from the front of a string isn't O(1)), we optimize the solution using a deque approach.

Approach: 1) Initialize an unordered_map to track the frequency of characters. 2) Use a deque for pushing characters, and update the result deque (res) with the current deque (temp) whenever we find a longer substring. 3) Use a while loop to reduce the frequency from the front, incrementing i, and removing characters from the temp deque as we no longer need them. 4) Return res.size() as we are interested in the length of the longest substring.

Time Complexity: O(N) Space Complexity: O(N)

I hope this helps to understand. Thank you!

Author

Ashish Kumar Sahoo

Definition in file longest_substring_without_repeating_characters.cpp.

Function Documentation

main()

int main

(

void

)

Main function.

Returns

0 on successful execution.

Definition at line 107 of file longest_substring_without_repeating_characters.cpp.

           {
    tests(); // run self-test implementations
    return 0;
}

tests()

static void tests ( )

static

Self-test implementations.

Returns

void

Definition at line 92 of file longest_substring_without_repeating_characters.cpp.

                    {
    Longest_Substring soln;
    assert(soln.lengthOfLongestSubstring("abcabcbb") == 3);
    assert(soln.lengthOfLongestSubstring("bbbbb") == 1);
    assert(soln.lengthOfLongestSubstring("pwwkew") == 3);
    assert(soln.lengthOfLongestSubstring("") == 0); // Test case for empty string
    assert(soln.lengthOfLongestSubstring("abcdef") == 6); // Test case for all unique characters
    assert(soln.lengthOfLongestSubstring("a") == 1); // Single character
    std::cout << "All test cases passed!" << std::endl;
}