Length of the longest substring without repeating characters in Java
The problem of finding the length of the longest substring without repeating characters is a classic algorithmic challenge that often arises in the context of string manipulation and pattern matching. This problem requires designing an efficient algorithm to determine the maximum length of a contiguous substring within a given string such that no character repeats within that substring.
Example 1:
Input
S = “abcabcbb”
Output
Length of the longest substring without repeating characters: 3
Explanation
“abc” is the longest substring without repeating characters among all the substrings with length 3.
Example 2:
Input
S = “books”
Output
Length of the longest substring without repeating characters: 3
Explanation
“oks” is the longest substring without repeating characters among all the substrings with length 3.
Approach 1: Brute Force Approach
In this approach we involve in exhaustively checking all possible substrings of the given input string and evaluating each substring to determine whether it contains any repeating characters. In the context of this algorithmic challenge, the brute force approach relies on a nested loop structure to systematically explore all possible substrings within the input string.
Algorithm
Step 1: Initialize Variables: Set maxLength to 0 (maximum length of the substring without repeating characters). Get the length of the input string n.
Step 2: Iterate over each index i from 0 to n - 1. For each i, iterate over each index j from i + 1 to n. Check Unique Characters: Within the nested loop, call the allUnique function to check if the characters in the substring from index i to j - 1 are all unique.
Step 3: If they are, update maxLength to the maximum of its current value and j - i. After both loops are completed, return the final value of maxLength. Function allUnique takes the input string s and two indices start and end.
Step 4: Create a HashSet to store characters and check uniqueness. Iterate from start to end - 1: Get the character at the current index.
Step 5: If the character is already in the HashSet, return false. Otherwise, add the character to the HashSet. If the loop completes, return true indicating all characters in the substring are unique.
Filename: LongestSubstringBruteForce.java
import java.util.HashSet;
public class LongestSubstringBruteForce {
public static int lengthOfLongestSubstringBruteForce(String s) {
int maxLength = 0;
int n = s.length();
for (int i = 0; i < n; i++) {
for (int j = i + 1; j <= n; j++) {
if (allUnique(s, i, j)) {
maxLength = Math.max(maxLength, j - i);
}
}
}
return maxLength;
}
private static boolean allUnique(String s, int start, int end) {
// Helper function to check if all characters in the substring are unique
HashSet<Character> set = new HashSet<>();
for (int i = start; i < end; i++) {
char ch = s.charAt(i);
if (set.contains(ch)) {
return false;
}
set.add(ch);
}
return true;
}
public static void main(String[] args) {
String input = "abcabcbb";
int result = lengthOfLongestSubstringBruteForce(input);
System.out.println("Length of the longest substring without repeating characters: " + result);
}
}
Output:
Length of the longest substring without repeating characters: 3
Time Complexity
The time complexity of the provided brute force algorithm is O(n^3), where 'n' is the length of the input string. The outer loop runs in O(n) time, and for each iteration of the outer loop, the inner loop runs in O(n) time, and the allUnique function also takes O(n) time in the worst case.
Space Complexity
The space complexity of the algorithm is O(min(n, m)), where 'n' is the length of the input string, and 'm' is the size of the character set (assuming ASCII characters). The primary space-consuming component is the HashSet used in the allUnique function, which can have a maximum of 'n' elements if all characters are unique.
Approach 2: Sliding Window Approach
The Sliding Window Approach is a powerful and widely used technique in computer science and algorithmic problem-solving, particularly in scenarios where there is a need to efficiently process and analyze a sequence of elements, such as characters in a string or numbers in an array. In this approach we involve in maintaining a dynamic "window" of elements within the input sequence and adjusting the window's boundaries as needed to optimize the solution to a specific problem.
Algorithm
Step 1: Initialize Variables: Set start and end pointers to 0. Initialize maxLength to 0 and create an empty charIndexMap (HashMap) to store the last index of each character.
Step 2: Iterate Through the String: While the end pointer is within the bounds of the string: Get the character at the current end index. Check if the character is already in charIndexMap and if its index is greater than or equal to start.
Step 3: If true, it means the character is repeated in the current window. Move start to skip the repeated character. Update the index of the current character in charIndexMap.
Step 4: Update maxLength to the maximum of its current value and the length of the current substring (end - start + 1). Increment the end pointer to consider the next character.
Step 5: Continue the process until the end pointer reaches the end of the string. The final result is the maximum length of the substring without repeating characters.
Filename: LongestSubstringSlidingWindow.java
import java.util.HashMap;
import java.util.Map;
public class LongestSubstringSlidingWindow {
public static int lengthOfLongestSubstring(String s) {
int maxLength = 0;
int start = 0;
Map<Character, Integer> charIndexMap = new HashMap<>();
for (int end = 0; end < s.length(); end++) {
char currentChar = s.charAt(end);
if (charIndexMap.containsKey(currentChar) && charIndexMap.get(currentChar) >= start) {
// If the character is repeated in the current window, move 'start' to skip it
start = charIndexMap.get(currentChar) + 1;
}
// Update the character's index in the map
charIndexMap.put(currentChar, end);
// Update the maximum length of the substring
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 without repeating characters: " + result);
}
}
Output:
Length of the longest substring without repeating characters: 3
Time Complexity
The time complexity of the Sliding Window Approach to finding the length of the longest substring without repeating characters is O(n), where 'n' is the length of the input string. The algorithm iterates through the string once using two pointers (start and end), and each character is processed at most twice (once by the end pointer and once by the start pointer).
Space Complexity
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 (assuming ASCII characters). The primary space-consuming component is the charIndexMap (HashMap) used to store the last index of each character encountered.
Approach 3: Optimized Sliding Window Approach
The Optimized Sliding Window Approach is an advanced and refined version of the classical sliding window technique, aiming to further improve efficiency and reduce unnecessary operations in algorithmic problem-solving. This approach is particularly valuable in scenarios where the traditional sliding window may involve redundant calculations or unnecessary iterations. The optimization often involves using additional data structures or adjusting the algorithmic logic to achieve a more efficient solution.
Algorithm
Step 1: Initialize Variables: Set start and end pointers to 0 and initialize maxLength to 0. Create an array charIndex to store the last index of each character (assuming ASCII characters). Initialize all elements of charIndex to -1 using Arrays.fill(charIndex, -1).
Step 2: Iterate Through the String: While the end pointer is within the bounds of the string: Get the character at the current end index.
Step 3: Update the start pointer to the maximum of its current value and the next index after the last occurrence of the current character (charIndex[currentChar] + 1). Update the last index of the current character in the charIndex array.
Step 4: Update maxLength to the maximum of its current value and the length of the current substring (end - start + 1). Increment the end pointer to consider the next character.
Step 5: Continue the process until the end pointer reaches the end of the string. The final result is the maximum length of the substring without repeating characters.
Filename: LongestSubstringOptimized.java
import java.util.Arrays;
public class LongestSubstringOptimized {
public static int lengthOfLongestSubstringOptimized(String s) {
int maxLength = 0;
int start = 0;
int[] charIndex = new int[128]; // Assuming ASCII characters
Arrays.fill(charIndex, -1);
for (int end = 0; end < s.length(); end++) {
char currentChar = s.charAt(end);
start = Math.max(start, charIndex[currentChar] + 1);
charIndex[currentChar] = end;
maxLength = Math.max(maxLength, end - start + 1);
}
return maxLength;
}
public static void main(String[] args) {
String input = "abcabcbb";
int result = lengthOfLongestSubstringOptimized(input);
System.out.println("Length of the longest substring without repeating characters: " + result);
}
}
Output:
Length of the longest substring without repeating characters: 3
Time Complexity
The time complexity of the Optimized Sliding Window Approach to finding the length of the longest substring without repeating characters is O(n), where 'n' is the length of the input string.
Space Complexity
The space complexity is O(1), constant space. The primary space-consuming component is the charIndex array of fixed size (128 for ASCII characters). The size of the array remains constant regard less of the input size, making the space complexity independent of the input length.