Finding the Longest Palindromic Substring

You are given a string s, your task is to find the longest palindromic substring in s. A palindromic substring is a substring that reads the same backward as forward.

Write a function longest_palindromic_substring(s: str) -> str that takes a string s and returns the longest palindromic substring in s.

If there are multiple palindromic substrings with the same length, return any one of them.

Examples:

Input: s = "babad"
Output: "bab" or "aba"

Input: s = "cbbd"
Output: "bb"

Explanation:

In the first example, “bab” and “aba” are both palindromic substrings of length 3.

In the second example, “bb” is the only palindromic substring of length 2.

Note:

The input string s will have at most length 1000.
The function should be case sensitive, i.e. “A” is different from “a”.
You can assume that the input string contains only printable ASCII characters.

Test Cases:

Test Case 1:

Input: s = "racecar"
Output: "racecar"

Test Case 2:

Input: s = "abcda"
Output: "a"

In Test Case 1, “racecar” is a palindromic substring of length 7.

In Test Case 2, “a” is the only palindrome

A Kotlin Code solution :

Kotlin

fun longestPalindromicSubstring(s: String): String {
    var maxLen = 0
    var start = 0
    var end = 0
    
    for (i in s.indices) {
        // check palindromic substrings with odd length
        var left = i
        var right = i
        
        while (left >= 0 && right < s.length && s[left] == s[right]) {
            if (right - left + 1 > maxLen) {
                maxLen = right - left + 1
                start = left
                end = right
            }
            left--
            right++
        }
        
        // check palindromic substrings with even length
        left = i
        right = i + 1
        
        while (left >= 0 && right < s.length && s[left] == s[right]) {
            if (right - left + 1 > maxLen) {
                maxLen = right - left + 1
                start = left
                end = right
            }
            left--
            right++
        }
    }
    
    return s.substring(start, end + 1)
}
fun main() {
    // Test Case 1
    val s1 = "racecar"
    val result1 = longestPalindromicSubstring(s1)
    println(result1) // Output: "racecar"
    
    // Test Case 2
    val s2 = "abcda"
    val result2 = longestPalindromicSubstring(s2)
    println(result2) // Output: "a"
}

Leave a Comment Cancel reply