Given a String, find the length of longest substring without any repeating character.

Example 1:

Input: s = ”abcabcbb”

Output: 3

Explanation: The answer is abc with length of 3.

Example 2:

Input: s = ”bbbbb”

Output: 1

Explanation: The answer is b with length of 1 units.

My solution works, but it isn't optimised. How can this be done in O(n) time?

#include<bits/stdc  .h>

using namespace std;

int solve(string str) {

  if(str.size()==0)
      return 0;
  int maxans = INT_MIN;
  for (int i = 0; i < str.length(); i  ) // outer loop for traversing the string
  {
    unordered_set < int > set;
    for (int j = i; j < str.length(); j  ) // nested loop for getting different string starting with str[i]
    {
      if (set.find(str[j]) != set.end()) // if element if found so mark it as ans and break from the loop
      {
        maxans = max(maxans, j - i);
        break;
      }
      set.insert(str[j]);
    }
  }
  return maxans;
}

int main() {
  string str = "abcsabcds";
  cout << "The length of the longest substring without repeating characters is " << 
  solve(str);
  return 0;
}

CodePudding user response：

Use a two pointer approach along with a hashmap here.

1. Initialise two pointers i = 0, j = 0 (i and j denote the left and right boundary of the current substring)
2. If the j-th character is not in the map, we can extend the substring. Add the j-th char to the map and increment j.
3. If the j-th character is in the map, we can not extend the substring without removing the earlier occurrence of the character. Remove the i-th char from the map and increment i.
4. Repeat this while j < length of string

This will have a time and space complexity of O(n).

CodePudding user response：

This code has time complexity O(N)

#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 = "thereisnoway";
  Solution obj;
  cout << "The length of the longest substring without repeating characters is " << obj.lengthofLongestSubstring(str);
  return 0;
}