Largest Substring Between Two Equal Characters in Java
Give a string s, and return the longest substring (without including the two characters) between any two equal characters. Give back -1 if there isn't a substring of that kind.
Characters that are consecutive within a string are called substrings.
Examples:
Example 1:
Input: s = “aa”
Output: 0
Explanation: The optimal substring here is an empty substring between the two ‘a’s.
Example 2:
Input: s = “abca”
Output: 2
Explanation: The optimal substring here is ‘bc’.
Example 3:
Input: s = “cbzxy”
Output: -1
Explanation: There are no characters that appear twice in s.
Approach 1: Using Index mapping approach
An approach similar to "Index Mapping" is utilized in the code that is provided. To start, an array called {charIndxMp} is initialized in order to record the last index of each alphabet character that appears in the input string {s}. The array's elements are all set to -1 by this initialization. Once the algorithm runs through the string, it subtracts the ASCII value of 'a' from each character to transfer it to an index in the array. A character's index is kept in the array if it has never been encountered before. The algorithm determines the length of the substring between the current index and the last index where a character appeared when the character appears again. This length is checked against the maximum length that is in effect right now, and updated if needed. The procedure effectively ascertains the maximum length of the substring between equal characters in a single trip of the string by upholding and constantly updating this index mapping. This method provides an effective solution to the problem by making the best use of the complexity of space and time.
Filename: MaxLength.java
import java.util.Arrays;
public class MaxLength
{
public int maxLengthBetweenEqualCharacters(String s)
{
int charIndxMp[] = new int[26];
Arrays.fill(charIndxMp, -1);
int maxSubLen = -1;
for(int indx = 0; indx < s.length(); indx++)
{
int currChar = s.charAt(indx) - 'a';
if(charIndxMp[currChar] != -1)
{
maxSubLen = Math.max(maxSubLen, indx - charIndxMp[currChar] - 1);
}
else
{
charIndxMp[currChar] = indx;
}
}
return maxSubLen;
}
public static void main(String[] args)
{
MaxLength maxlength = new MaxLength();
String testString = "abcaabb";
int maxLength = maxlength.maxLengthBetweenEqualCharacters(testString);
System.out.println("Maximum length of substring between equal characters: " + maxLength);
}
}
Output:
Maximum length of substring between equal characters: 4
Complexity analysis:
Time complexity: The time complexity of the program is O(n), n is the size of the given string s.
Space complexity: The space complexity of the program is O(26).
Approach 2: Using array indexing method
Step 1: Keep track of each character's last occurrence index.
Step 2: Next, proceed from the front and compare each character index with its last occurrence index.
Step 3: Continue monitoring the maximum.
Filename: MaximumLen.java
public class MaximumLen {
public static int maxLengthBetweenEqualCharacters(String s) {
int[] last = new int[26];
int ans = -1;
for(int i = 0; i < s.length(); ++i)
last[s.charAt(i) - 'a'] = i;
for(int i = 0; i < s.length(); ++i)
ans = Math.max(ans, last[s.charAt(i) - 'a'] - i - 1);
return ans;
}
public static void main(String[] args) {
String testString = "abcaabb";
int maxLength = maxLengthBetweenEqualCharacters(testString);
System.out.println("Maximum length of substring between equal characters: " + maxLength);
}
}
Output:
Maximum length of substring between equal characters: 4
Complexity analysis:
Time complexity: The time complexity of the program is O(n), n is the size of the given string s.
Space complexity: The space complexity of the program is O(26).
Approach 3: Using optimal approach
Step 1: Store the first character index in the first tarverse.
step 2: In the second traverse, locate the last index and update the boolean brrr and arr distances.In []()
step 3: Represent our max distance by the max value in arr.
Filename: LargestSubstringOptimal.java
import java.util.Arrays;
public class LargestSubstringOptimal
{
public int maxLengthBetweenEqualCharacters(String s)
{
int[] arr = new int[26];
boolean[] brr = new boolean[26];
Arrays.fill(arr, -1);
for (int i = 0; i < s.length(); i++) {
if (arr[s.charAt(i) - 'a'] == -1) {
arr[s.charAt(i) - 'a'] = i;
}
}
for (int j = s.length() - 1; j >= 0; j--) {
if (!brr[s.charAt(j) - 'a']) {
arr[s.charAt(j) - 'a'] = j - arr[s.charAt(j) - 'a'] - 1;
brr[s.charAt(j) - 'a'] = !brr[s.charAt(j) - 'a'];
}
}
int max = -1;
for (int x : arr) max = Math.max(x, max);
return max;
}
public static void main(String[] args) {
LargestSubstringOptimal obj = new LargestSubstringOptimal();
String testString = "abcaabb";
int maxLength = obj.maxLengthBetweenEqualCharacters(testString);
System.out.println("Maximum length of substring between equal characters: " + maxLength);
}
}
Output:
Maximum length of substring between equal characters: 4
Complexity analysis:
Time complexity: The time complexity of the program is O(N), n is the size of the given string s.
Space complexity: The space complexity of the program is O(N).