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 = “neveropen”, 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 palindromebool 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 chint 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 codeint main(){ string str = "lapqooqpqpl"; int n = str.length(); char ch = 'p'; cout << maxLenPalindrome(str, n, ch); return 0;} |
Java
// Java implementation of the approachclass 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 palindromedef 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 chdef 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 codestr = "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:
6
Time Complexity: O(n3) 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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
