Longest Substring without repeating characters

Problem

Given a string, find the longest substring with unique characters

Sample Input

"abcdd"

Sample Output

4

Explanation

The longest substring with unique characters is "abcd" resulting 4 unique letters.

Approach

The idea is to scan the string from left to right, keeping track of the longest non-repeating character substring seen so far. When traversing the string, we need two indexes to determine the length of the current window. 1) Ending index, j : The current index is used as the ending index of the current character. 2) Starting index, i If the current character was not present in the previous window, this variable is the same as in the previous window. To determine whether or not the current character was present in the previous window, we store the last index of each character in an array prev[] . If prev[string[j]] + 1 is greater than the previous start, the start index i is updated. Otherwise, we keep the same i .

Complexity Analysis

The time complexity is O(N), and the space complexity is almost O(1) since the number of characters will not exceed 26.

C++ Programming

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

int solve(string str)
{
    int n = str.size();

    int ans = 0; // result

    vector<int> prev(Size, -1);

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

    // Move end of current window
    for (int j = 0; j < n; j++) 
    {
        i = max(i, prev[str[j]] + 1);

        // Update result if we get a larger window
        ans = max(ans, j - i + 1);

        // Update last index of j.
        prev[str[j]] = j;
    }

    return ans;
}

int main()
{
    string str = "abcdd";

    int ans = solve(str);

    cout << ans;

    return 0;
}

Output

4

Java Programming

import java.util.*;

public class Solution {
    static final int Size = 256;

    static int solve(String str)
    {
        int n = str.length();

        int ans = 0; // result

        // last index of all characters is initialized
        // as -1
        int [] prev = new int[Size];

        Arrays.fill(prev, -1);

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

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

            i = Math.max(i, prev[str.charAt(j)] + 1);

            // Update result if we get a larger window
            ans = Math.max(ans, j - i + 1);

            // Update last index of j.
            prev[str.charAt(j)] = j;
        }
        return ans;
    }

    public static void main(String[] args)
    {
        String str = "abcdd";

        int len = solve(str);

        System.out.println(len);
    }
}

Output

4

Python Programming

def solve(s):
    # last index of every character
    prev = {}
    ans = 0

    # starting index of current
    # window to calculate ans
    ini = 0

    for i in range(0, len(s)):
        if s[i] in prev:
            ini = max(ini, prev[s[i]] + 1)

        # Update result if we get a larger window
        ans = max(ans, i-ini + 1)

        # Update last index of current char.
        prev[s[i]] = i

    return ans

s = "abcdd"
length = solve(s)
print(length)

Output

4

People are also reading:

• Dutch National Flag Problem
• Construction of an Expression Tree
• Print a two-dimensional view of a Binary Tree
• In-place vs out-of-place algorithms
• Maximum Sum Circular Subarray
• Find K-th Smallest Element in BST
• Check if directed graph is connected
• Minimum Edit Distance
• Diameter of a Binary Tree
• Reverse a Linked List