1.
Introduction
2.
Problem Statement
3.
Brute force approach
3.1.
Code in C++
3.2.
Complexity Analysis
4.
Sliding window approach
4.1.
Code in C++
4.2.
Complexity Analysis
5.
Optimized Sliding window approach
5.1.
Code in C++
5.2.
Complexity Analysis
6.
6.1.
What is the sliding window technique?
6.2.
Which two-pointer technique is used in the quick sort algorithm?
6.3.
What is a binary search algorithm?
7.
Conclusion
Last Updated: Mar 27, 2024

# Longest Substring Without Repeating Characters

Competitive programming
Free guided path
16 chapters
99+ problems

## Introduction

Strings are one of the most elementary data structures. At first, they may seem a bit complicated and a tad bit hard to manipulate, but, when you once get used to it, it is just as simple as manipulating any other array that has numbers in it. A mastery over strings could help you solve numerous problems that have been asked in a wide range of technical interviews even in big tech companies. In this article, we will take a look at one such problem.

## Problem Statement

We are given a string S consisting of English letters, digits, and symbols. Our task is to find the length of the largest continuous substring from the given string in which no characters are repeated, i.e. all characters are unique.

Examples:

Input : S= “abbcbaca”

Output : 3

Input : S= “codingninjas”

Output: 6

Recommended: Try the Problem yourself before moving on to the solution.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

## Brute force approach

The idea of this approach is simple: we check all the substrings of the given string and check whether it contains unique characters or repeating characters.

There are a total of n*(n+1)/2 substrings of a string of length n.

Steps:

• We first declare a max_length variable and initialize it with 0.

• Now, we explore all the substrings of the given string using two nested loops:
• Outer loop from (i=0 to n-1) and an inner loop from (j=i to n-1). The idea is to pick a starting character from the outer loop and find all the substrings starting with that character.

• After that, we check whether all the characters in the substring are unique or not with the areDifferent() function.

• If the areDifferent() function returns true, we update the max_length.

• Finally, return the value stored in max_length.

Steps for areDifferent() function

• To check whether the substrings contain unique characters or not, we create a vis[256] array (because the ASCII codes of all the characters and symbols lie in the 0-255 range) and initialize false to every index. It stores the status of all characters, whether it is visited or not.

• We go through each character and check whether it is visited or not. If it is visited, we return false. If no characters are visited twice, we return true.

### Code in C++

``````#include<bits/stdc++.h>
using namespace std;

bool areDifferent(string S, int i, int j)
{
bool vis[256];

for (int i = 0; i < 256; i++)
vis[i] = false;

for (int k = i; k <= j; k++)
{
if (vis[S[k]] == true)
return false;
vis[S[k]] = true;
}

return true;

}

int longestSubstr(string S)
{
int max_length = 0;

int n = S.length();

for (int i = 0; i < n; i++)
{
for (int j = i; j < n; j++)
{
if (areDifferent(S, i, j))
max_length = max(max_length, j - i + 1);
}
}

return max_length;
}
int main()
{
string S;
cin >> S;
cout << longestSubstr(S) << endl;
return 0;
}``````

Input

``codingninjas``

Output

``6``

### Complexity Analysis

Time Complexity

We are using two nested loops and an areDifferent() function inside it, so the overall time complexity becomes O(n2)*O(n) = O(n3)

Space complexity

It is O(1) as we are using a constant size of vis[] array and some variables.

Also check out - Substr C++

## Sliding window approach

We can further optimize the above solution because, during the loop, if substring S[i to j-1] is already checked, then for substring S[i to j], we only need to check whether S[j] is present in the substring S[i to j-1] or not.

We can use the vis[256] array to check whether it is present in the substring or not.

Steps:

• We first declare a max_length and i variable and initialize them with 0.

• We run an outer loop till i<n to check all the substrings starting from character S[i].

• Inside the loop, we initialize j=i, and both are 0 initially, and we also use a vis[256] array to store the status of characters in the current window [i, j).

• Now, we run an inner loop till j<n && vis[S[j]]==false.

• If S[j] is not present in the current window [i, j), we mark it as visited and keep track of max substring length. Now we move the window to one right by incrementing j.

• If S[j] is already visited, we increment i by 1 and mark the ith character not visited.

When the left end of the string reaches the end, i.e., i=n, we return the value stored in max_length.

### Code in C++

``````#include<bits/stdc++.h>
using namespace std;
int longestSubstr(string S)
{
int max_length = 0;

int n = S.length();

int i = 0;

while (i < n)
{
bool vis[256] = {false};
int j = i;
while (j < n && vis[S[j]] == false)
{
max_length = max(max_length, j - i + 1);
vis[S[j]] = true;
j++;
}
vis[S[i]] = false;
i++;
}

return max_length;
}

int main()
{
string S;
cin >> S;
cout << longestSubstr(S) << endl;
return 0;
}``````

Input

``abbcbaca``

Output

``3``

### Complexity Analysis

Time Complexity

We are using two nested loops, so the time complexity is O(n2)

Space complexity

It is O(1) as we use a constant size 256 of vis[] array and some variables.

## Optimized Sliding window approach

Idea

If the characters in window [i,j] are unique, then the characters in window [i+1, j] will be as well. As a result, there is no need to start with a new window of size 1 or reset j=i in the next iteration of the outer loop.

Steps

• Using the pointers i and j, scan the string from left to right. Maintain an unordered set to keep track of visited characters, as well as the max length variable.

• If S[j] isn't in the set, we insert it and slide the current window by one by incrementing the j pointer. We also update the max_length variable.

• If S[j] already exists in the set, we delete it and move the window to the right by incrementing pointer i.

• If any of the pointers reaches the end of the string, the process will be terminated. We return the value of the max length variable.

### Code in C++

``````#include<bits/stdc++.h>
using namespace std;
int longestSubstr(string S)
{
int max_length = 0;
int n = S.length();
int i = 0, j = 0;
if (n == 0)
return 0;
unordered_set<int> vis;
while (i < n && j < n)
{
if (vis.find(S[j]) == vis.end())
{
vis.insert(S[j]);
j++;
max_length = max(max_length, j - i);
}
else
{
vis.erase(vis.find(S[i]));
i++;
}
}

return max_length;
}

int main()
{
string S;
cin >> S;
cout << longestSubstr(S) << endl;
return 0;
}``````

Input

``codingninjas``

Output

``6``

### Complexity Analysis

Time Complexity

We are using only one while loop, so the time complexity is O(n)

Space complexity

It requires O(n) space for the unordered set.

Check out this problem - Smallest Distinct Window .

### What is the sliding window technique?

As the name implies, this technique involves taking a subset of data from a given array or string and expanding or contracting that subset to satisfy certain conditions, hence the sliding effect.

### Which two-pointer technique is used in the quick sort algorithm?

Most quicksort implementations take advantage of the fact that you can partition by keeping two pointers: one moving in from the left and one from the right.

### What is a binary search algorithm?

Binary search is a fast algorithm for finding a single item in a sorted list of items. It works by repeatedly dividing the portion of the list that could contain the item in half until you've reduced the number of possible locations to just one.

## Conclusion

So, this article discussed the fundamental brute force approach, the sliding window approach, which is better than the brute force approach, and the optimized sliding window version with linear time complexity of the Longest Substring Without Repeating Characters problem and their C++ code.

Recommended Problems:

Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, Basics of C++, Basics of Java, Basics of Python, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

In case of any comments or suggestions, feel free to post them in the comments section.

Guided path
Free
Competitive programming
16 chapters
217+ Problems