The concept is to keep a window of unique personalities. The window opens as single character. We keep widening the window on the right side till we come upon unique personalities. We erase characters from the left side of the display when we observe a recurring character. We maintain the maximum length window under observation.
The comprehensive instructions are below:
Starting two points left and right with 0, define the current window under consideration.
Extensive the current window, the right pointer goes from left to right.
The character at right pointer is indicated as visited should it not be visited.
Should the character at right pointer be visited, it indicates a repeated character. Marking visited characters as false, the left cursor advances to the right until the repeated character is no longer part of the current window.
Calculated length of the current window (right – left + 1) determines the response modification.
C++
// C++ code to find the largest substring with
// non-repeating characters using Sliding Window
#include <bits/stdc++.h>
using namespace std;
int longestUniqueSubstr(string& s) {
// if string length is 0
if (s.length() == 0)
return 0;
// if string length 1
if (s.length() == 1)
return 1;
// if string length is more than 1
int maxLength = 0;
vector<bool>visited(256, false);
// left and right pointer of sliding window
int left = 0, right = 0;
while (right < s.length()) {
// If the character is repeated, move left pointer
// to the right and mark visited characters as false
// until the repeating character is no longer part
// of the current window.
while (visited[s[right]] == true) {
visited[s[left]] = false;
left++;
}
visited[s[right]] = true;
// The length of the current window (right - left + 1)
// is calculated and answer is updated accordingly.
maxLength = max(maxLength, (right - left + 1));
right++;
}
return maxLength;
}
int main() {
string s = "geeksforgeeks";
cout << longestUniqueSubstr(s);
return 0;
}C
// C code to find the largest substring with
// non-repeating characters using Sliding Window
#include <stdio.h>
#include <string.h>
#include <stdbool.h>
int longestUniqueSubstr(const char* s) {
// if string length is 0
if (strlen(s) == 0)
return 0;
// if string length 1
if (strlen(s) == 1)
return 1;
// if string length is more than 1
int maxLength = 0;
bool visited[256] = { false };
// left and right pointer of sliding window
int left = 0, right = 0;
int n = strlen(s); // Store the length of the string
while (right < n) {
// If the character is repeated, move left pointer
// to the right and mark visited characters as false
// until the repeating character is no longer part
// of the current window.
while (visited[s[right]] == true) {
visited[s[left]] = false;
left++;
}
visited[s[right]] = true;
// The length of the current window (right - left + 1)
// is calculated and answer is updated accordingly.
if(maxLength < (right - left + 1))
maxLength = (right - left + 1);
right++;
}
return maxLength;
}
int main() {
const char* s = "geeksforgeeks";
printf("%d\n", longestUniqueSubstr(s));
return 0;
}Java
// Java code to find the largest substring with
// non-repeating characters using Sliding Window
class GfG {
// Function to find the length of the largest substring
// with non-repeating characters using Sliding Window
static int longestUniqueSubstr(String s) {
// if string length is 0
if (s.length() == 0)
return 0;
// if string length 1
if (s.length() == 1)
return 1;
// if string length is more than 1
int maxLength = 0;
boolean[] visited = new boolean[256];
// left and right pointer of sliding window
int left = 0, right = 0;
while (right < s.length()) {
// If the character is repeated, move left pointer
// to the right and mark visited characters as false
// until the repeating character is no longer part
// of the current window.
while (visited[s.charAt(right)]) {
visited[s.charAt(left)] = false;
left++;
}
visited[s.charAt(right)] = true;
// The length of the current window (right - left + 1)
// is calculated and answer is updated accordingly
maxLength = Math.max(maxLength, (right - left + 1));
right++;
}
return maxLength;
}
public static void main(String[] args) {
String s = "geeksforgeeks";
System.out.println(longestUniqueSubstr(s));
}
}Python
# Python code to find the largest substring with
# non-repeating characters using Sliding Window
def longestUniqueSubstr(s):
# if string length is 0
if len(s) == 0:
return 0
# if string length 1
if len(s) == 1:
return 1
# if string length is more than 1
maxLength = 0
visited = [False] * 256
# left and right pointer of sliding window
left = 0
right = 0
while right < len(s):
# If the character is repeated, move left pointer
# to the right and mark visited characters as false
# until the repeating character is no longer part
# of the current window.
while visited[ord(s[right])] == True:
visited[ord(s[left])] = False
left += 1
visited[ord(s[right])] = True
# The length of the current window (right - left + 1)
# is calculated and answer is updated accordingly.
maxLength = max(maxLength, right - left + 1)
right += 1
return maxLength
if __name__ == "__main__":
s = "geeksforgeeks"
print(longestUniqueSubstr(s))JS
// Javascript code to find the largest substring with
// non-repeating characters using Sliding Window
function longestUniqueSubstr(s) {
// if string length is 0
if (s.length === 0)
return 0;
// if string length 1
if (s.length === 1)
return 1;
// if string length is more than 1
let maxLength = 0;
let visited = new Array(256).fill(false);
// left and right pointer of sliding window
let left = 0, right = 0;
while (right < s.length) {
// If the character is repeated, move left pointer
// to the right and mark visited characters as false
// until the repeating character is no longer part
// of the current window.
while (visited[s.charCodeAt(right)] === true) {
visited[s.charCodeAt(left)] = false;
left++;
}
visited[s.charCodeAt(right)] = true;
// The length of the current window (right - left + 1)
// is calculated and answer is updated accordingly.
maxLength = Math.max(maxLength, right - left + 1);
right++;
}
return maxLength;
}
const s = "geeksforgeeks";
console.log(longestUniqueSubstr(s));