A substring is a contiguous sequence of characters within a string. In this article, we will discuss approaches to finding the longest substring in a string, with their implementation in C++, Java, and Python.
Longest Substring Without Repeating Characters Problem
In the Longest Substring without Repeating Character problem, we are given a string of length n and we have to find the length of the longest substring with no repeating characters.
For Example:
Input: Favtutor
Output: 5
Explanation: favtu
The substring “favtu” does not contain any repeating character and is the longest such substring.
Before moving to an optimized approach, let’s do it with brute force. This method involves employing two loops: one for traversing the string and another nested loop for identifying different substrings. Subsequently, we examine each substring individually, checking each element. If an element is not found, we store it in a HashSet; otherwise, we break from the loop and increment the count.
Here are the Steps to be followed in this Approach:
- We will run an outer loop that traverses the string to consider different starting points for substrings and an inner loop will start from the index ongoing in the outer loop and iterates through the string.
- We will declare an unordered set to keep track of the characters in the current substring
- At every step, we will check If the character at position j is already in the set, which means we found a repeating character. And we will update the max length by comparing it with the current length.
- After this, we will break from the inner loop as we have considered all the substrings starting from position i.
- After both loops, the function returns the maximum length of the substring without repeating characters.
HashSet is also useful to solve the Valid Sudoku problem.
The Time complexity of this approach is O(N2), where N is the length of the input string because we are using nested loops. The Space Complexity of this approach is O(N) where N is the size of the Set taken for storing the elements.
Optimal Approach
To find the longest substring in a string without repeating characters, we will map each character with the latest index of that character and maintain the frequency of each character.
Here are the steps involved in this Approach:
- Firstly we will declare a vector to store the last index of each character in the ASCII range (256 characters). Initialized with -1.
- Now we will declare the two pointers left and right for the sliding window.
- Now we will run a while loop till the right pointer is less than the size of the string.
- If the current character is already in the substring (i.e., its last index is not -1), we will adjust the left to the last index of that character + 1 position and update the last index of the current character in the vector.
- At the end of each step, we will update the length of the longest substring without repeating characters and move the right pointer to expand the window.
C++ Code
Below is the C++ program to find the longest substring without repeating characters:
#include <bits/stdc++.h>
using namespace std;
int lengthofLongestSubstring(string s) {
vector<int> mpp(256, -1); // Vector to store the last index of each character in the ASCII range (256 characters)
int left = 0, right = 0; // Pointers for the sliding window
int n = s.size(); // Length of the input string
int len = 0; // Length of the longest substring without repeating characters
while (right < n) {
// If the current character is already in the substring
if (mpp[s[right]] != -1)
left = max(mpp[s[right]] + 1, left); // Move the left pointer to the next position after the last occurrence of the character
mpp[s[right]] = right; // Update the last index of the current character
len = max(len, right - left + 1); // Update the length of the longest substring
right++; // Move the right pointer to expand the window
}
return len; // Return the length of the longest substring without repeating characters
}
int main() {
string str = "favtutor";
// Call the function and print the result
cout << "The length of the longest substring without repeating characters is " << lengthofLongestSubstring(str);
return 0;
}Python Code
We can implement it in Python as well:
def length_of_longest_substring(s):
mpp = [-1] * 256 # List to store the last index of each character in the ASCII range (256 characters)
left = 0
right = 0
n = len(s) # Length of the input string
max_len = 0 # Length of the longest substring without repeating characters
while right < n:
# If the current character is already in the substring
if mpp[ord(s[right])] != -1:
left = max(mpp[ord(s[right])] + 1, left) # Move the left pointer to the next position after the last occurrence of the character
mpp[ord(s[right])] = right # Update the last index of the current character
max_len = max(max_len, right - left + 1) # Update the length of the longest substring
right += 1 # Move the right pointer to expand the window
return max_len # Return the length of the longest substring without repeating characters
# Example Usage
str_value = "favtutor"
print("The length of the longest substring without repeating characters is", length_of_longest_substring(str_value))Java Code
The same solution can be implemented in Java also:
import java.util.Arrays;
public class LengthOfLongestSubstring {
public static int lengthOfLongestSubstring(String s) {
int[] mpp = new int[256]; // Array to store the last index of each character in the ASCII range (256 characters)
Arrays.fill(mpp, -1);
int left = 0;
int right = 0;
int n = s.length(); // Length of the input string
int maxLen = 0; // Length of the longest substring without repeating characters
while (right < n) {
// If the current character is already in the substring
if (mpp[s.charAt(right)] != -1) {
left = Math.max(mpp[s.charAt(right)] + 1, left); // Move the left pointer to the next position after the last occurrence of the character
}
mpp[s.charAt(right)] = right; // Update the last index of the current character
maxLen = Math.max(maxLen, right - left + 1); // Update the length of the longest substring
right++; // Move the right pointer to expand the window
}
return maxLen; // Return the length of the longest substring without repeating characters
}
public static void main(String[] args) {
// Example Usage
String strValue = "favtutor";
System.out.println("The length of the longest substring without repeating characters is " + lengthOfLongestSubstring(strValue));
}
}Output:
The length of the longest substring without repeating characters is 5The Time Complexity of the algorithm is O(n), where n is the length of the input string because we are iterating through the string using two pointers (left and right) in a single pass. The Space Complexity is constant, O(1), or O(256) in terms of the character set.
Conclusion
In conclusion, we have discussed the longest substring without repeating the character leetcode problem using the optimal approach by using the concept of sliding window and also implemented their code in C++, Java, and Python. And also discussed their time and space complexity.
