Maximum length palindromic substring such that it starts and ends with given char

0 0 6 minutes read

Given a string str and a character ch, the task is to find the longest palindromic sub-string of str such that it starts and ends with the given character ch.
Examples:

Input: str = “lapqooqpqpl”, ch = ‘p’
Output: 6
“pqooqp” is the maximum length palindromic
sub-string that starts and ends with ‘p’.
Input: str = “zambiatek”, ch = ‘k’
Output: 1
“k” is the valid sub-string.

Approach: For every possible index pair (i, j) such that str[i] = str[j] = ch check whether the sub-string str[i…j] is palindrome or not. For all the found palindromes, store the length of the longest palindrome found so far.
Below is the implementation of the above approach:

C++

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function that returns true if
// str[i...j] is a palindrome
bool isPalindrome(string str, int i, int j)
{
    while (i < j) {
        if (str[i] != str[j])
            return false;
        i++;
        j--;
    }
    return true;
}
 
// Function to return the length of the
// longest palindromic sub-string such that
// it starts and ends with the character ch
int maxLenPalindrome(string str, int n, char ch)
{
    int maxLen = 0;
 
    for (int i = 0; i < n; i++) {
 
        // If current character is
        // a valid starting index
        if (str[i] == ch) {
 
            // Instead of finding the ending index from
            // the beginning, find the index from the end
            // This is because if the current sub-string
            // is a palindrome then there is no need to check
            // the sub-strings of smaller length and we can
            // skip to the next iteration of the outer loop
            for (int j = n - 1; j >= i; j--) {
 
                // If current character is
                // a valid ending index
                if (str[j] == ch) {
 
                    // If str[i...j] is a palindrome then update
                    // the length of the maximum palindrome so far
                    if (isPalindrome(str, i, j)) {
                        maxLen = max(maxLen, j - i + 1);
                        break;
                    }
                }
            }
        }
    }
    return maxLen;
}
 
// Driver code
int main()
{
    string str = "lapqooqpqpl";
    int n = str.length();
    char ch = 'p';
 
    cout << maxLenPalindrome(str, n, ch);
 
    return 0;
}

Java

// Java implementation of the approach
class GFG
{
     
    // Function that returns true if 
    // str[i...j] is a palindrome 
    static boolean isPalindrome(String str, 
                               int i, int j) 
    {
        while (i < j)
        {
            if (str.charAt(i) != str.charAt(j))
            {
                return false;
            }
            i++;
            j--;
        }
        return true;
    }
 
    // Function to return the length of the 
    // longest palindromic sub-string such that 
    // it starts and ends with the character ch 
    static int maxLenPalindrome(String str, int n, char ch) 
    {
        int maxLen = 0;
 
        for (int i = 0; i < n; i++)
        {
 
            // If current character is 
            // a valid starting index 
            if (str.charAt(i) == ch)
            {
 
                // Instead of finding the ending index from 
                // the beginning, find the index from the end 
                // This is because if the current sub-string 
                // is a palindrome then there is no need to check 
                // the sub-strings of smaller length and we can 
                // skip to the next iteration of the outer loop 
                for (int j = n - 1; j >= i; j--) 
                {
 
                    // If current character is 
                    // a valid ending index 
                    if (str.charAt(j) == ch) 
                    {
 
                        // If str[i...j] is a palindrome then update 
                        // the length of the maximum palindrome so far 
                        if (isPalindrome(str, i, j)) 
                        {
                            maxLen = Math.max(maxLen, j - i + 1);
                            break;
                        }
                    }
                }
            }
        }
        return maxLen;
    }
 
    // Driver code 
    public static void main(String[] args) 
    {
        String str = "lapqooqpqpl";
        int n = str.length();
        char ch = 'p';
 
        System.out.println(maxLenPalindrome(str, n, ch));
    }
}
 
// This code is contributed by Princi Singh

Python3

# Python implementation of the approach
 
# Function that returns true if
# str[i...j] is a palindrome
def isPalindrome(str, i, j):
    while (i < j):
        if (str[i] != str[j]):
            return False;
        i+=1;
        j-=1;
    return True;
 
 
# Function to return the length of the
# longest palindromic sub-string such that
# it starts and ends with the character ch
def maxLenPalindrome(str, n, ch):
    maxLen = 0;
 
    for i in range(n):
 
        # If current character is
        # a valid starting index
        if (str[i] == ch):
 
            # Instead of finding the ending index from
            # the beginning, find the index from the end
            # This is because if the current sub-string
            # is a palindrome then there is no need to check
            # the sub-strings of smaller length and we can
            # skip to the next iteration of the outer loop
            for j in range(n-1,i+1,-1):
                # If current character is
                # a valid ending index
                if (str[j] == ch):
 
                    # If str[i...j] is a palindrome then update
                    # the length of the maximum palindrome so far
                    if (isPalindrome(str, i, j)):
                        maxLen = max(maxLen, j - i + 1);
                        break;
 
    return maxLen;
 
# Driver code
str = "lapqooqpqpl";
n = len(str);
ch = 'p';
 
print(maxLenPalindrome(str, n, ch));
     
# This code is contributed by 29AjayKumar

C#

// C# implementation of the approach 
using System;
 
class GFG 
{ 
     
    // Function that returns true if 
    // str[i...j] is a palindrome 
    static bool isPalindrome(string str, 
                            int i, int j) 
    { 
        while (i < j) 
        { 
            if (str[i] != str[j]) 
            { 
                return false; 
            } 
            i++; 
            j--; 
        } 
        return true; 
    } 
 
    // Function to return the length of the 
    // longest palindromic sub-string such that 
    // it starts and ends with the character ch 
    static int maxLenPalindrome(string str, int n, char ch) 
    { 
        int maxLen = 0; 
 
        for (int i = 0; i < n; i++) 
        { 
 
            // If current character is 
            // a valid starting index 
            if (str[i] == ch) 
            { 
 
                // Instead of finding the ending index from 
                // the beginning, find the index from the end 
                // This is because if the current sub-string 
                // is a palindrome then there is no need to check 
                // the sub-strings of smaller length and we can 
                // skip to the next iteration of the outer loop 
                for (int j = n - 1; j >= i; j--) 
                { 
 
                    // If current character is 
                    // a valid ending index 
                    if (str[j] == ch) 
                    { 
 
                        // If str[i...j] is a palindrome then update 
                        // the length of the maximum palindrome so far 
                        if (isPalindrome(str, i, j)) 
                        { 
                            maxLen = Math.Max(maxLen, j - i + 1); 
                            break; 
                        } 
                    } 
                } 
            } 
        } 
        return maxLen; 
    } 
 
    // Driver code 
    public static void Main() 
    { 
        string str = "lapqooqpqpl"; 
        int n = str.Length; 
        char ch = 'p'; 
 
        Console.WriteLine(maxLenPalindrome(str, n, ch)); 
    } 
} 
 
// This code is contributed by AnkitRai01 

Javascript

<script>
      // JavaScript implementation of the approach
      // Function that returns true if
      // str[i...j] is a palindrome
      function isPalindrome(str, i, j) {
        while (i < j) {
          if (str[i] !== str[j]) {
            return false;
          }
          i++;
          j--;
        }
        return true;
      }
 
      // Function to return the length of the
      // longest palindromic sub-string such that
      // it starts and ends with the character ch
      function maxLenPalindrome(str, n, ch) {
        var maxLen = 0;
 
        for (var i = 0; i < n; i++) {
          // If current character is
          // a valid starting index
          if (str[i] === ch) {
            // Instead of finding the ending index from
            // the beginning, find the index from the end
            // This is because if the current sub-string
            // is a palindrome then there is no need to check
            // the sub-strings of smaller length and we can
            // skip to the next iteration of the outer loop
            for (var j = n - 1; j >= i; j--) {
              // If current character is
              // a valid ending index
              if (str[j] === ch) {
                // If str[i...j] is a palindrome then update
                // the length of the maximum palindrome so far
                if (isPalindrome(str, i, j)) {
                  maxLen = Math.max(maxLen, j - i + 1);
                  break;
                }
              }
            }
          }
        }
        return maxLen;
      }
 
      // Driver code
      var str = "lapqooqpqpl";
      var n = str.length;
      var ch = "p";
 
      document.write(maxLenPalindrome(str, n, ch));
    </script>

Output:

Time Complexity: O(n³)
Space Complexity: O(1)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!