# Longest Substring without repeating characters

Posted in  Vinay Khatri
Last updated on November 5, 2022

## Problem

Given a string, find the longest substring with unique characters

#### Sample Input

`"abcdd"`

`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;
}```

`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);
}
}```

`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)```

`4`