Longest Substring Without Repeat

Back to home

𝑻𝒂𝒃𝒍𝒆 𝒐𝒇 𝑪𝒐𝒏𝒕𝒆𝒏𝒕

Problem Statement: Longest Substring Without Repeat
Naive Approach
Approach 2: Using Sliding Window

Logicmojo - Updated Aug 28, 2021

Problem Statement: Longest Substring Without Repeat

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

Example: s: "logicmojo"

Output: 6 i.e (logicm)

Approach 1: Brute Force

We can consider all substrings one by one and check for each substring whether it contains all unique characters or not. There will be n*(n+1)/2 substrings. Whether a substring contains all unique characters or not can be checked in linear time by scanning it from left to right and keeping a map of visited characters. Time complexity of this solution would be O(n³) i.e. not the optimal one so we need to optimise it.

Approach 2: Efficient(Sliding Window)

The basic idea is, keep a hashmap which stores the characters in string as keys and their positions as values, and keep two pointers which define the max substring. move the right pointer to scan through the string , and meanwhile update the hashmap. If the character is already in the hashmap, then move the left pointer to the right of the same character last found just same as concept of sliding window i.e. slide the window if character repeats. Note that the two pointers can only move forward.

C++ Implementation:

#include <bits/stdc++.h>

using namespace std;
class Solution {
  public:
    int lengthofLongestSubstring(string s) {
      vector < int > mpp(256, -1);

      int left = 0, right = 0;
      int n = s.size();
      int len = 0;
      while (right < n) {
        if (mpp[s[right]] != -1)
          left = max(mpp[s[right]] + 1, left);

        mpp[s[right]] = right;

        len = max(len, right - left + 1);
        right++;
      }
      return len;
    }
};

int main() {
  string str = "takeUforward";
  Solution obj;
  cout << "The length of the longest substring without repeating characters is " << obj.lengthofLongestSubstring(str);
  return 0;
}

Python Implementation:

class Solution:
    def lengthOfLongestSubstring(self, s):
        seen = {}
        l = 0
        output = 0
        for r in range(len(s)):
            """
            If s[r] not in seen, we can keep #increasing the window size by moving right pointer
            """
            if s[r] not in seen:
                output = max(output,r-l+1)
            """
            There are two cases if s[r] in seen:
            case1: s[r] is inside the current window, we need to change the window by moving left pointer to 
#seen[s[r]] + 1.
            case2: s[r] is not inside the current window, we can keep increase the window
            """
            else:
                if seen[s[r]] < l:
                    output = max(output,r-l+1)
                else:
                    l = seen[s[r]] + 1
            seen[s[r]] = r
        return output
ob1 = Solution()
print(ob1.lengthOfLongestSubstring("logicmojo"))

Time Complexity: O(n) n is the length of the input string. It will iterate n times to get the result.

Auxiliary Space: O(m) m is the number of unique characters of the input. We need a hashmap to store unique characters.

With this article at Logicmojo, you must have the complete idea of solving Longest Substring Without Repeat problem.