Find the Length of the Longest Symmetric Substring

Refactor Java code safely — and automatically — with OpenRewrite.

Refactoring big codebases by hand is slow, risky, and easy to put off. That’s where OpenRewrite comes in. The open-source framework for large-scale, automated code transformations helps teams modernize safely and consistently.

Each month, the creators and maintainers of OpenRewrite at Moderne run live, hands-on training sessions — one for newcomers and one for experienced users. You’ll see how recipes work, how to apply them across projects, and how to modernize code with confidence.

Join the next session, bring your questions, and learn how to automate the kind of work that usually eats your sprint time.

Regression testing is an important step in the release process, to ensure that new code doesn't break the existing functionality. As the codebase evolves, we want to run these tests frequently to help catch any issues early on.

The best way to ensure these tests run frequently on an automated basis is, of course, to include them in the CI/CD pipeline. This way, the regression tests will execute automatically whenever we commit code to the repository.

In this tutorial, we'll see how to create regression tests using Selenium, and then include them in our pipeline using GitHub Actions:, to be run on the LambdaTest cloud grid:

>> How to Run Selenium Regression Tests With GitHub Actions

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.

The code backing this article is available on GitHub. Once you're logged in as a Baeldung Pro Member, start learning and coding on the project.