Longest substring containing distinct elements

Problem Statement: Given a string consisting of alphabetic characters. Print the length of the longest substring containing distinct elements.

Examples:

Example 1:
Input: s = "wewr"
Output:
 Length of the longest substring : 3
Explanation: The longest substring is “ewr” (length : 3).

Example 2:
Input: s = "abcd"
Output: Length of the longest substring : 4
Explanation: The longest substring is “abcd” (length : 4).

Solution

Disclaimer: Don’t jump directly to the solution, try it out yourself first.

Solution 1:

Intuition:

Every time we see an element in an array, we check whether that character is already present, if present we reduce the substring length or else we increase it.

Approach:

  • We need some variables like start (starting index of the substring), end (ending index), maxLen(max length found so far).
  • We traverse the string one by one, trying to insert the current character in the substring formed so far.
  • When we take a character we try to find whether it is already present in the substring we considered.
  • If present, we set the start variable to next position, meaning that hereafter the substring starts from the next position(now we have eliminated the duplicates).
  • Else we add the current character in the substring(we are not literally adding, we just increment the length).
  • And as usual everytime check whether the current substring length is maximum and update the global maximum.

Code:

C++ Code

#include<bits/stdc++.h>

using namespace std;

int longestSubstrWithoutDupliBF(string s, int n) {

  int start = 0, end = -1, maxLen = 0;
  for (int i = 0; i < n; i++) {
    int j = start;
    for (; j <= end && s[j] != s[i]; j++);

    if (j <= end)
      start = j + 1;

    end++;
    maxLen = max(maxLen, end - start + 1);
  }
  return maxLen;
}

int main() {

  string s = "wewr";
  int n = s.length();

  cout << "Length of the longest substring : " << longestSubstrWithoutDupliBF(s, n);

  return 0;
}

Output: Length of the longest substring : 3

Time Complexity: O(n^2), traversing all the elements takes O(n) time, and checking the substring for duplicates for a particular character takes O(n).

Space Complexity: O(1), we are not using any extra space.

Java Code

import java.util.*;

public class Solution {

  public static void main(String[] args) {
    String s = "wewr";
    int n = s.length();

    System.out.println("Length of the longest substring : " + 
    longestSubstrWithoutDupliBF(s, n));
  }

  public static int longestSubstrWithoutDupliBF(String s, int n) {

    int start = 0, end = -1, maxLen = 0;
    for (int i = 0; i < n; i++) {
      int j;
      for (j = start; j <= end && s.charAt(j) != s.charAt(i); j++);

      if (j <= end)
        start = j + 1;

      end++;
      maxLen = Math.max(maxLen, end - start + 1);
    }
    return maxLen;
  }

}

Output: Length of the longest substring : 3

Time Complexity: O(n^2), traversing all the elements takes O(n) time, and checking the substring for duplicates for a particular character takes O(n).

Space Complexity: O(1), we are not using any extra space.

Solution 2:

Intuition:

We are taking extra time to search for duplicates in the above approach, we can reduce the search using an array or set. We’ll use arrays here.

Approach:

  • We have to do the same things as we did in the previous approach. We’ll use an array to store the positions of the characters in the substring. 
  • When traversing the string, if we found the character at some position in the substring, we edit the array(which stores the indexes) to -1 for all the elements from the start index to the current element’s index.
  • This basically means that, since the current character is already present somewhere in the array, we are trying to remove characters until the current character’s previous position is found. Because hereafter we’ll include the current character.
  • Thus we are getting rid of duplicates.

Code:

C++ Code

#include <bits/stdc++.h>

using namespace std;

int longestSubstrWithoutDupliOptimal(string s, int n) {
  int start = 0, end = -1, maxLen = 0;
  int present[26] = {
    -1
  };

  for (int i = 0; i < 26; i++)
    present[i] = -1;

  for (int i = 0; i < n; i++) {
    int character = s[i], prevFoundIndex = present[character - 'a'];
    end++;

    for (int j = start; j <= prevFoundIndex; j++)
      present[s[j] - 'a'] = -1;

    if (prevFoundIndex != -1)
      start = prevFoundIndex + 1;

    present[character - 'a'] = i;
    maxLen = max(maxLen, end - start + 1);
  }
  return maxLen;
}

int main() {
  string s = "wewr";
  int n = s.length();

  cout << "Length of the longest substring : " << longestSubstrWithoutDupliOptimal
  (s, n);
  return 0;
}

Output: Length of the longest substring : 3

Time Complexity: O(2n) ~ O(n), in the worst case, we’ll be traversing each element at least twice.

Space Complexity: O(1), even though we are using an extra array, we have only lowercase alphabetic characters in the string, so at max, we’ll be storing only 26 characters irrespective of input size.

Java Code

import java.util.*;

public class Solution {

  public static void main(String[] args) {
    String s = "wewr";
    int n = s.length();

    System.out.println("Length of the longest substring : " + 
    longestSubstrWithoutDupliOptimal(s, n));
  }

  public static int longestSubstrWithoutDupliOptimal(String s, int n) {
    int start = 0, end = -1, maxLen = 0;
    int[] present = new int[26];

    Arrays.fill(present, -1);

    for (int i = 0; i < n; i++) {
      int character = s.charAt(i), prevFoundIndex = present[character - 'a'];
      end++;

      for (int j = start; j <= prevFoundIndex; j++)
        present[s.charAt(j) - 'a'] = -1;

      if (prevFoundIndex != -1)
        start = prevFoundIndex + 1;

      present[character - 'a'] = i;
      maxLen = Math.max(maxLen, end - start + 1);
    }
    return maxLen;
  }

}

Output: Length of the longest substring : 3

Time Complexity: O(2n) ~ O(n), in the worst case, we’ll be traversing each element at least twice.

Space Complexity: O(1), even though we are using an extra array, we have only lowercase alphabetic characters in the string, so at max, we’ll be storing only 26 characters irrespective of input size.

Special thanks to Prathap P for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article