The problem of finding the longest substring without repeating characters is a common problem in computer science and can be found in various coding interviews and competitions. The task is to find the longest substring in a given string that does not contain any repeating characters.
For example, given the string “abcabcbb”, the longest substring without repeating characters would be “abc”, with a length of 3. Similarly, given the string “bbbbb” the longest substring without repeating characters would be “b”, with a length of 1.
Approach 1:
There are several ways to solve this problem. One common approach is to use a sliding window algorithm. This approach involves maintaining a window of characters and moving the window through the input string while keeping track of the characters in the window. If a repeating character is found, the window is moved to the right and the character is removed from the window. The length of the window is updated if a longer substring is found.
Leet Code: Longest Substring Without Repeating Characters Java | JavaScript | CPP | Python Solution
Here is a sample Python implementation of the sliding window approach:
Certainly! Here’s the equivalent code for the lengthOfLongestSubstring function in C++, Java, Python, and JavaScript:
C++: sliding window algorithm
#include <iostream>
#include <string>
#include <unordered_set>
using namespace std;
int lengthOfLongestSubstring(string s) {
unordered_set<char> charSet;
int maxLength = 0;
int i = 0, j = 0;
while (j < s.length()) {
if (charSet.find(s[j]) == charSet.end()) {
charSet.insert(s[j]);
j++;
maxLength = max(maxLength, j - i);
} else {
charSet.erase(s[i]);
i++;
}
}
return maxLength;
}
Leet Code 1658. Minimum Operations to Reduce X to Zero (Medium)
Java: sliding window algorithm
import java.util.HashSet;
import java.util.Set;
public class Main {
public static int lengthOfLongestSubstring(String s) {
Set<Character> charSet = new HashSet<>();
int maxLength = 0;
int i = 0, j = 0;
while (j < s.length()) {
if (!charSet.contains(s.charAt(j))) {
charSet.add(s.charAt(j));
j++;
maxLength = Math.max(maxLength, j - i);
} else {
charSet.remove(s.charAt(i));
i++;
}
}
return maxLength;
}
public static void main(String[] args) {
String input = "abcabcbb";
int result = lengthOfLongestSubstring(input);
System.out.println("Length of the longest substring: " + result);
}
}Python: sliding window algorithm
def lengthOfLongestSubstring(s: str) -> int:
char_set = set()
max_length = 0
i = 0
j = 0
while j < len(s):
if s[j] not in char_set:
char_set.add(s[j])
j += 1
max_length = max(max_length, j - i)
else:
char_set.remove(s[i])
i += 1
return max_length
Leet Code : longest common prefix string C++ ,java , Python Solution
JavaScript: sliding window algorithm
function lengthOfLongestSubstring(s) {
const charSet = new Set();
let maxLength = 0;
let i = 0;
let j = 0;
while (j < s.length) {
if (!charSet.has(s[j])) {
charSet.add(s[j]);
j++;
maxLength = Math.max(maxLength, j - i);
} else {
charSet.delete(s[i]);
i++;
}
}
return maxLength;
}
Approach 2:
Another approach is to use a hashmap to keep track of the last seen index of each character in the input string. The key idea behind this algorithm is to use a hashmap to keep track of the last seen index of each character in the input string. The variable “start “keeps track of the starting index of the current substring, and the variable “max_length “keeps track of the maximum length of substring seen so far.
The hashmap approach to solving the problem of finding the longest substring without repeating characters is based on the idea of using a hashmap to keep track of the last seen index of each character in the input string. By maintaining a record of the last seen index of each character, we can easily determine if a given character is a repeat, and if so, where the last occurrence of that character was in the input string.
Here’s how the algorithm works:
- Initialize a variable
startto keep track of the starting index of the current substring, and a variable “max_length” to keep track of the maximum length of substring seen so far. - Create an empty hashmap to store the last seen index of each character in the input string.
- Iterate through the input string one character at a time.
- For each character, check if it has been seen before. If it has, update the
startvariable to be one greater than the last seen index of that character. - Update the “
max_length“ variable to be the maximum of the current “max_length“and the difference between the current index and thestartvariable. - Store the current index in the hashmap for the current character.
- Return the value of ‘
max_length‘as the final result.
The time complexity of this approach is O(n) and the space complexity is O(min(n, m)) where n is the length of the input string and m is the size of the character set.
Here is a sample C++ implementation of this approach:
int lengthOfLongestSubstring(string s) {
unordered_map<char, int> char_map;
int max_length = 0;
int start = 0;
for (int i = 0; i < s.size(); i++) {
if (char_map.count(s[i]) && char_map[s[i]] >= start) {
max_length = max(max_length, i - start);
start = char_map[s[i]] + 1;
}
char_map[s[i]] = i;
}
return max(max_length, (int)s.size() - start);
}
Java: hashmap
import java.util.HashMap;
import java.util.Map;
public class Main {
public static int lengthOfLongestSubstring(String s) {
Map<Character, Integer> charMap = new HashMap<>();
int maxLength = 0;
int start = 0;
for (int i = 0; i < s.length(); i++) {
if (charMap.containsKey(s.charAt(i)) && charMap.get(s.charAt(i)) >= start) {
maxLength = Math.max(maxLength, i - start);
start = charMap.get(s.charAt(i)) + 1;
}
charMap.put(s.charAt(i), i);
}
return Math.max(maxLength, s.length() - start);
}
public static void main(String[] args) {
String input = "abcabcbb";
int result = lengthOfLongestSubstring(input);
System.out.println("Length of the longest substring: " + result);
}
}Python: hashmap
def lengthOfLongestSubstring(s: str) -> int:
char_map = {}
max_length = 0
start = 0
for i in range(len(s)):
if s[i] in char_map and char_map[s[i]] >= start:
max_length = max(max_length, i - start)
start = char_map[s[i]] + 1
char_map[s[i]] = i
return max(max_length, len(s) - start)
input_str = "abcabcbb"
result = lengthOfLongestSubstring(input_str)
print("Length of the longest substring:", result)JavaScript: hashmap
function lengthOfLongestSubstring(s) {
const charMap = new Map();
let maxLength = 0;
let start = 0;
for (let i = 0; i < s.length; i++) {
if (charMap.has(s[i]) && charMap.get(s[i]) >= start) {
maxLength = Math.max(maxLength, i - start);
start = charMap.get(s[i]) + 1;
}
charMap.set(s[i], i);
}
return Math.max(maxLength, s.length - start);
}
const input = "abcabcbb";
const result = lengthOfLongestSubstring(input);
console.log("Length of the longest substring: " + result);Approach 3:
Another approach to solve the problem of finding the longest substring without repeating characters is to use two pointers. This approach uses two pointers, one to traverse the input string and the other to keep track of the substring without repeating characters.
The idea behind this approach is to use one pointer, called “start”, to mark the start of the current substring, and another pointer, called “end”, to traverse the input string. As we traverse the input string, we use a hashmap to keep track of the last seen index of each character. If we encounter a character that has been seen before, we update the “start” pointer to be the last seen index of that character plus one. We then update the maximum length of the substring without repeating characters if the current substring is longer than the previous maximum.
C++ : two pointers
int lengthOfLongestSubstring(string s) {
int start = 0, max_length = 0;
unordered_map<char, int> char_map;
for (int end = 0; end < s.size(); end++) {
if (char_map.count(s[end]) && char_map[s[end]] >= start) {
start = char_map[s[end]] + 1;
}
char_map[s[end]] = end;
max_length = max(max_length, end - start + 1);
}
return max_length;
}
Java: two pointers
import java.util.HashMap;
import java.util.Map;
public class Main {
public static int lengthOfLongestSubstring(String s) {
int start = 0;
int maxLength = 0;
Map<Character, Integer> charMap = new HashMap<>();
for (int end = 0; end < s.length(); end++) {
if (charMap.containsKey(s.charAt(end)) && charMap.get(s.charAt(end)) >= start) {
start = charMap.get(s.charAt(end)) + 1;
}
charMap.put(s.charAt(end), end);
maxLength = Math.max(maxLength, end - start + 1);
}
return maxLength;
}
public static void main(String[] args) {
String input = "abcabcbb";
int result = lengthOfLongestSubstring(input);
System.out.println("Length of the longest substring: " + result);
}
}Python: two pointers
def lengthOfLongestSubstring(s: str) -> int:
start = 0
max_length = 0
char_map = {}
for end in range(len(s)):
if s[end] in char_map and char_map[s[end]] >= start:
start = char_map[s[end]] + 1
char_map[s[end]] = end
max_length = max(max_length, end - start + 1)
return max_length
input_str = "abcabcbb"
result = lengthOfLongestSubstring(input_str)
print("Length of the longest substring:", result)JavaScript: two pointers
function lengthOfLongestSubstring(s) {
let start = 0;
let maxLength = 0;
const charMap = new Map();
for (let end = 0; end < s.length; end++) {
if (charMap.has(s[end]) && charMap.get(s[end]) >= start) {
start = charMap.get(s[end]) + 1;
}
charMap.set(s[end], end);
maxLength = Math.max(maxLength, end - start + 1);
}
return maxLength;
}
const input = "abcabcbb";
const result = lengthOfLongestSubstring(input);
console.log("Length of the longest substring: " + result);This solution has a time complexity of O(n) and space complexity of O(min(n, m)), where n is the length of the input string and m is the size of the character set.
The two-pointer approach is efficient in the sense that it only iterates through the input string once, thus having a linear time complexity. This approach is also relatively simple to understand and implement, making it a popular choice among interviewers and competitive programmers.