Longest substring without repeating characters-Last Index

The method saves the last indices of already seen characters. Initialized as one character, the concept is to keep a window of different characters. We keep widening the window on the right side till we come upon different personalities. When we see a repeating character, we look for the last index of that repeated character:

We adjust the starting index of the current window to last index of repeated character + 1 to eliminate the repeated character if last index of repeated character > starting index of the current window.
The window size stays the same if last index of repeated character is already beyond the current window, starting index of the current window indicates that this is so.
The biggest window size will be our result after iteratively over every character.

C++

// C++ code to find the largest substring with
// non-repeating characters using last index of 
// repeated character

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

int longestUniqueSubstr(string& s) {
    int n = s.size();

    int res = 0;

    // last index of all characters is initialized as -1
    vector<int> lastIndex(256, -1);

    // Initialize start of current window
    int start = 0;

    // Move end of current window
    for (int end = 0; end < n; end++) {

        // Find the last index of s[end]
        // Update starting index of current window as
        // maximum of current value of end and last index + 1
        start = max(start, lastIndex[s[end]] + 1);

        // Update result if we get a larger window
        res = max(res, end - start + 1);

        // Update last index of s[end]
        lastIndex[s[end]] = end;
    }
    return res;
}

int main() {
    string s = "geeksforgeeks";
    cout << longestUniqueSubstr(s);
    return 0;
}

C

// C code to find the largest substring with
// non-repeating characters using last index of 
// repeated character

#include <stdio.h>
#include <string.h>
#include <limits.h>

int longestUniqueSubstr(const char* s) {
    int n = strlen(s);
    int res = 0;

    // last index of all characters is initialized as -1
    int lastIndex[256];
    for (int i = 0; i < 256; i++) {
        lastIndex[i] = -1;
    }

    // Initialize start of current window
    int start = 0;

    // Move end of current window
    for (int end = 0; end < n; end++) {
      
        // Find the last index of s[end]
        // Update starting index of current window as
        // maximum of current value of start and last index + 1
        start = (start > lastIndex[s[end]] + 1) ? start : 
                                          (lastIndex[s[end]] + 1);

        // Update result if we get a larger window
        res = (res > end - start + 1) ? res : (end - start + 1);

        // Update last index of s[end]
        lastIndex[s[end]] = end;
    }
    return res;
}

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 last index of 
// repeated character

class GfG {

    static int longestUniqueSubstr(String s) {
        int n = s.length();

        int res = 0;

        // last index of all characters is initialized as -1
        int[] lastIndex = new int[256];
        for (int i = 0; i < 256; i++) {
            lastIndex[i] = -1;
        }

        // Initialize start of current window
        int start = 0;

        // Move end of current window
        for (int end = 0; end < n; end++) {
          
            // Find the last index of s[end]
            // Update starting index of current window as
            // maximum of current value of start and last index + 1
            start = Math.max(start, lastIndex[s.charAt(end)] + 1);

            // Update result if we get a larger window
            res = Math.max(res, end - start + 1);

            // Update last index of s[end]
            lastIndex[s.charAt(end)] = end;
        }

        return res;
    }

    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 last index of 
# repeated character


def longestUniqueSubstr(s):
    n = len(s)
    
    res = 0

    # last index of all characters is initialized as -1
    last_index = [-1] * 256

    # Initialize start of current window
    start = 0

    # Move end of current window
    for end in range(n):
        
        # Find the last index of s[end]
        # Update starting index of current window as
        # maximum of current value of start and last index + 1
        start = max(start, last_index[ord(s[end])] + 1)

        # Update result if we get a larger window
        res = max(res, end - start + 1)

        # Update last index of s[end]
        last_index[ord(s[end])] = end

    return res

s = "geeksforgeeks"
print(longestUniqueSubstr(s))

JS

// JavaScript code to find the largest substring with
// non-repeating characters using last index of 
// repeated character

function longestUniqueSubstr(s) {
    const n = s.length;
    let res = 0;

    // last index of all characters is initialized as -1
    const lastIndex = new Array(256).fill(-1);

    // Initialize start of current window
    let start = 0;

    // Move end of current window
    for (let end = 0; end < n; end++) {
        // Find the last index of s[end]
        // Update starting index of current window as
        // maximum of current value of start and last index + 1
        start = Math.max(start, lastIndex[s.charCodeAt(end)] + 1);

        // Update result if we get a larger window
        res = Math.max(res, end - start + 1);

        // Update last index of s[end]
        lastIndex[s.charCodeAt(end)] = end;
    }

    return res;
}

const s = "geeksforgeeks";
console.log(longestUniqueSubstr(s));

Output

7