Longest Even Length Substring in Java
The longest even-length substring in Java refers to finding a contiguous substring of even length within a given string such that the substring is the longest among all possible even-length substrings. The characters in the substring are consecutive and not necessarily distinct.
Example 1:
Input: abbaabba
Output: Longest even length substring: abbaabba
Explanation:
For the input "abbaabba", the longest even length substring is "abbaabba" itself because the first half "abba" is equal to the second half "abba".
Example 2:
Input: abcdef
Output: Longest even length substring:
Explanation:
For the input "abcdef", there is no even length substring, so that the output will be an empty string:
Approach:
Step 1: Initialize two variables, maxLength and result, to keep track of the length of the longest even-length substring found so far and the actual substring, respectively.
Step 2: The outer loop iterates through each index i in the input string.
The inner loop iterates through each index j starting from i + 1 with a step size 2.
Step 3: Calculate the midpoint (mid) as (j - i + 1) / 2.
Extract two substrings:
- firstHalf: Substring from index i to i + mid.
- secondHalf: Substring from index i + mid to j + 1.
Step 4: Check if firstHalf is equal to secondHalf (i.e., both halves are identical) and if the length of the current substring (j - i + 1) is greater than the current maxLength.
Step 5: If the above condition is true, update maxLength with the length of the current substring and update the result with the actual substring from the input.
Step 6: After both loops, return the result representing the longest even-length substring found in the input string.
Filename: LongestEvenLengthSubstring.java
public class LongestEvenLengthSubstring {
public static void main(String[] args) {
String input = "abbaabba";
String result = findLongestEvenLengthSubstring(input);
System.out.println("Longest even length substring: " + result);
}
public static String findLongestEvenLengthSubstring(String input) {
int maxLength = 0;
String result = "";
for (int i = 0; i < input.length() - 1; i++) {
for (int j = i + 1; j < input.length(); j += 2) {
int mid = (j - i + 1) / 2;
String firstHalf = input.substring(i, i + mid);
String secondHalf = input.substring(i + mid, j + 1);
if (firstHalf.equals(secondHalf) && (j - i + 1) > maxLength) {
maxLength = j - i + 1;
result = input.substring(i, j + 1);
}
}
}
return result;
}
}
Output:
Longest even length substring: abbaabba
Complexity analysis:
The time complexity of the code is O(n^3), where 'n' is the length of the input string.
The space complexity is O(1) or constant.