1. Introduction
Determining the length of the longest symmetric substring poses a common challenge in string manipulation tasks.
In this tutorial, we’ll discuss two Java approaches for efficiently solving this problem.
2. Understanding Symmetric Substrings
The symmetric substring is a substring that reads the same backward and forward. For example, in the string “abba“, the longest symmetric substring is “abba“, which reads the same forward and backward with a maximum length of 4.
3. Symmetric Substring Expansion Approach
This approach utilizes a sliding window technique to identify the longest symmetric substring within the given string efficiently. Essentially, the algorithm iterates through the string, expanding from the middle while ensuring symmetry.
Let’s delve into the implementation:
private int findLongestSymmetricSubstringUsingSymmetricApproach(String str) {
int maxLength = 1;
// Approach implementation
}
In this method, we initialize maxLength to 1, representing the default length of a palindrome substring. Then, we’ll iterate over all possible substrings in the input string as follows:
for (int i = 0; i < str.length(); i++) {
for (int j = i; j < str.length(); j++) {
int flag = 1;
for (int k = 0; k < (j - i + 1) / 2; k++) {
if (str.charAt(i + k) != str.charAt(j - k)) {
flag = 0;
break;
}
}
if (flag != 0 && (j - i + 1) > maxLength) {
maxLength = j - i + 1;
}
}
}
Within each substring, we utilize a nested loop to compare characters from both ends towards the center, checking for symmetry. Moreover, if a substring is found to be symmetric (flag is not 0) and its length exceeds maxLength, we update maxLength with the new length.
Finally, we’ll return the maximum length of a symmetric substring found in the input string as follows:
return maxLength;
4. Using the Brute Force Approach
The brute-force method provides a straightforward solution to the problem. Here’s how we can implement this approach:
private int findLongestSymmetricSubstringUsingBruteForce(String str) {
if (str == null || str.length() == 0) {
return 0;
}
int maxLength = 0;
for (int i = 0; i < str.length(); i++) {
for (int j = i + 1; j <= str.length(); j++) {
String substring = str.substring(i, j);
if (isPalindrome(substring) && substring.length() > maxLength) {
maxLength = substring.length();
}
}
}
return maxLength;
}
Here, we exhaustively examine all possible substrings within the input string to identify potential palindromic substrings. Additionally, this process involves iterating through each character of the string, considering it as a potential starting point for a substring.
For each starting position, the method iterates through subsequent characters to construct substrings of varying lengths.
Once we construct a substring, we pass it to the isPalindrome() method to determine whether it is a palindrome as follows:
private boolean isPalindrome(String str) {
int left = 0;
int right = str.length() - 1;
while (left < right) {
if (s.charAt(left) != s.charAt(right)) {
return false;
}
left++;
right--;
}
return true;
}
This method scrutinizes the substring by comparing characters from both ends toward the center, ensuring that the characters mirror each other symmetrically.
If the substring passes the palindrome test and its length surpasses the current maxLength, it is deemed a candidate for the longest palindrome substring. In this case, the method updates the maxLength variable to reflect the new maximum length.
5. Conclusion
In this article, we discussed how to handle the symmetric substring expansion methods, highlighting the importance of specific requirements such as input size and computational efficiency.
As always, the complete code samples for this article can be found over on GitHub.
