Longest Substring without repeating characters

Posted in

Longest Substring without repeating characters

Vinay Khatri
Last updated on September 26, 2022

    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:

    Leave a Comment on this Post

    0 Comments