Longest Substring Between Any Pair of Occurrences of Similar Characters in Java
Given a string, the task is to find the length of the longest substring that occurs between any two occurrences of the same character in the string.
Example 1
Input: S = “accabbacc”
Output: 6
Explanation: The longest substring satisfying the required conditions is “cabbac”, which lies between S[1](= ‘c’) and s[8](= ‘c’).
Example 2
Input: S = “aab”
Output: 0
Explanation: There are no equal characters in the input string, so the output is 0.
Example 3
Input: S = "abbabbc"
Output: 3
Explanation: The longest substring satisfying the required conditions is "bab", which lies between S[2] (= 'b') and S[4] (= 'b').
Approach 1: Using Brute Force
A brute force approach involves iterating through each character in the string and finding the first and last occurrences of the character. It then calculates the length of the substring between these occurrences and updates the maximum length encountered.
Algorithm
Step 1: Iterate through each character in the string.
Step 2: For each character, find its first and last occurrence in the string using indexOf and lastIndexOf methods.
Step 3: Calculate the length of the substring between these occurrences.
Step 4: Update the maximum length encountered.
Filename: LongestSubstringUsingBruteForce.java
public class LongestSubstringUsingBruteForce { // Function to find the length of the longest substring between any pair of similar characters public static int longestSubstringLength(String s) { int maxLength = 0; // Iterate through each character in the string for (int i = 0; i < s.length(); i++) { char ch = s.charAt(i); // Find the first and last occurrence of the current character int firstIndex = s.indexOf(ch); int lastIndex = s.lastIndexOf(ch); // Calculate the length of the substring between occurrences int length = lastIndex - firstIndex - 1; // Update the maximum length if needed maxLength = Math.max(maxLength, length); } return maxLength; } public static void main(String[] args) { String input = "accabbacc"; int result = longestSubstringLength(input); System.out.println("Length of longest substring: " + result); } }
Output
Length of longest substring: 6
Time Complexity: The time complexity of this approach is O(n^2), where n is the length of the input string. This is because for each character, we search for its first and last occurrences using linear search.
Space Complexity: The space complexity of this approach is O(1). This is because we only use a constant amount of extra space for variables like maxLength, firstIndex, lastIndex, and length.
Approach 2: Using HashMap
An approach uses a HashMap to store the index of the last occurrence of each character. It iterates through the string, updating the HashMap with each character's index and calculating the length of the longest substring.
Algorithm
Step 1: Initialize a HashMap to store the last occurrence index of each character.
Step 2: Iterate through the string.
Step 3: If the character is already in the HashMap, calculate the difference between the current index and the last occurrence index.
Step 4: Update the maximum difference found.
Step 5: If the character is not in the HashMap, add it with its current index.
Step 6: Return the maximum difference found minus 1 to get the correct length of the substring.
Filename: LongestSubstringUsingHashMap.java
import java.util.*; public class LongestSubstringUsingHashMap { // Function to find the length of the longest substring between equal characters public static int longestBetweenEqualCharacters(String S) { int n = S.length(); MaplastIndexMap = new HashMap<>(); int res = -1; for (int i = 0; i < n; i++) { char c = S.charAt(i); if (lastIndexMap.containsKey(c)) { // Calculate the difference between the current index and the last occurrence index int diff = i - lastIndexMap.get(c); // Update the maximum difference found res = Math.max(diff, res); } else { // Add a character to the HashMap with its current index lastIndexMap.put(c, i); } } return res - 1; // to get the correct length } public static void main(String[] args) { String s = "accabbacc"; System.out.println("Length of longest substring: " +longestBetweenEqualCharacters(s)); } }
Output
Length of longest substring: 6
Time Complexity: The time complexity of this approach is O(n), where n is the length of the input string.
Space Complexity: The space complexity is also O(n) due to the HashMap storing at most all distinct characters in the string.