Length Of The Longest Substring With Non-Repeating Characters in C++

Today we’ll learn to find the length of the longest substring with non-repeating characters. This problem is one of the most popular interview problems. It has also been asked during the coding round of various FAANG companies (should we call them MAANG already?). We will use the sliding window concept to solve this problem. The sliding window concept is one of the most typical yet crucial concepts you’ll ever come across while doing DSA. Without any further delay, let’s go through the problem statement.

Problem Statement

You are given a string as input. Find out the length of the largest substring that contains every character only once.

Consider the following examples,

String: ABABC
Solution: ABC
Length: 3

String: Apple
Solution: ple
Length: 3

String: Mango
Solution: Mango
Length: 5

String: Vaibhav
Solution: Vaibh or ibhav
Length: 5

String: CakeWalk
Solution: CakeW
Length: 5

String: AppleMango
Solution: pleMango
Length: 8

String: NewDelhi
Solution: wDelhi
Length: 6

Concept of Finding the Length Of The Longest Substring With Non-Repeating Characters

The brute force approach takes O(N³) time complexity. This means that our solution will be limited to 1< N < 100, where N denotes the length of the string. The sliding window concept states that if we have a window of some size. Then based on the need, we will either contract the window or expand it. Below is the pseudocode to demonstrate the approach that we’ll follow.

We’ll start iterating on the string from i = 0.
Before we move to the next character, we’ll check for its presence in the current window.
- If the character is not present in the window, expand the window one step towards the right.
- Else, do the following.
  - Check for the position of the upcoming character in the current window.
  - To check for the position, we’ll either use a hashmap or an array as a map.
  - Suppose the length of the current window is L, and the position of the character is P.
    - Move the left end of the window from the position: (i – L) to (i – (L – P)).
    - Now expand the window by one step on the right.
During each iteration of the loop, we’ll check for the length of the window
- Update the length as:
- max_length = max(max_length, current_length);

Let’s now code this algorithm and check the output.

Algorithm for Finding the Length Of The Longest Substring With Non-Repeating Characters

Let’s now look at the code for finding the Length Of The Longest Substring With Non-Repeating Characters using C++

int longest_substring(string s)
{
	int length = s.size();
	
	if(length == 0)
		return 0;

	int current_len = 1;
	int max_len = 1;

	// create the array to map the characters
	// and mark each character as unvisited
	vector <int> visited(256, -1);

	// handling the first character
	visited[s[0]] = 1;

	// now start iterating over the string
	for(int i = 1; i < length; i++)
	{
		// check for its last occurrence
		int last_occ = visited[s[i]];
		
		// if the character is not present
		// in the current window, just take it
		// case: Expansion
		if(last_occ == -1 || (i - last_occ) > current_len)
		{
			current_len++;
			max_len = max(max_len, current_len);
		}

		// case: Expansion + Contraction
		else
		{
			max_len = (max_len, current_len);
			current_len = i - last_occ;

		}

		// update the location of current element in the vector
		visited[s[i]] = i;
	}

	return max_len;
}

Length Of The Longest Substring With Non-Repeating Characters C++ Program

#include <iostream>
#include <vector>

using namespace std;

int longest_substring(string s)
{
	int length = s.size();
	
	if(length == 0)
		return 0;

	int current_len = 1;
	int max_len = 1;

	// create the array to map the characters
	// and mark each character as unvisited
	vector <int> visited(256, -1);

	// handling the first character
	visited[s[0]] = 1;

	// now start iterating over the string
	for(int i = 1; i < length; i++)
	{
		// check for its last occurrence
		int last_occ = visited[s[i]];
		
		// if the character is not present
		// in the current window, just take it
		// case: Expansion
		if(last_occ == -1 || (i - last_occ) > current_len)
		{
			current_len++;
			max_len = max(max_len, current_len);
		}

		// case: Expansion + Contraction
		else
		{
			max_len = (max_len, current_len);
			current_len = i - last_occ;

		}

		// update the location of current element in the vector
		visited[s[i]] = i;
	}

	return max_len;
}

int main()
{
	cout << "Enter the string" << endl;
	string s;
	cin >> s;

	cout << "The length of the longest substring with non-repeating characters is: " << longest_substring(s) << endl;

	return 0;
}

Output

Conclusion

In this article, we learned to use the sliding window approach, and using this approach we solved the given problem. Notice that the time complexity of the algorithm boils down to O(N) because of the presence of just a single for loop. This is the magic of the sliding window approach, it’s O(N²) more efficient than the brute force approach. That’s all for today, thanks for reading.