Given two integers N and K (K ? N), the task is to obtain a string of length N such that maximum length of a palindromic substring of this string is K.
Examples:
Input: N = 5, K = 3
Output: “abacd”
Explanation: Palindromic substrings are “a”, “b”, “c”, “d” and “aba”. Therefore, the longest palindromic substring from the given string is of length 3.Input: N = 8, K = 4
Output: “abbacdef”
Explanation: Palindromic substrings are “a”, “b”, “c”, “d”, “e”, “f”, “bb”, “abba”. Therefore, the longest palindromic substring from the given string is of length 4.
Approach: The idea is based on the following observation that the string of any length made up of a single character is always palindromic, e.g. {‘a’, ‘bbbbb’, ‘ccc’}. So, in order to generate a string with required conditions, print ‘a’ K times such that it has a longest palindromic substring of length K fill the remaining N – K slots by a non-palindromic sequence.
Follow the steps below to solve the problem:
- Print ‘a’ exactly K times.
- Consider a non-palindromic sequence, say “bcd”.
- Print the string.
Below is the implementation of the above approach:
C++
// C++ program to implement the above approach#include <bits/stdc++.h>using namespace std;// Function to generate a string of// length N having longest palindromic// substring of length Kvoid string_palindrome(int N, int K){ // Fill first K characters with 'a' for (int i = 0; i < K; i++) cout << "a"; // Stores a non-palindromic sequence // to be repeated for N - k slots string s = "bcd"; // Print N - k remaining characters for (int i = 0; i < N - K; i++) cout << s[i % 3];}// Driver Codeint main(){ // Given N and K int N = 5, K = 3; string_palindrome(N, K); return 0;} |
Java
// Java program to implement the above approachimport java.util.*;class GFG{// Function to generate a String of// length N having longest palindromic// subString of length Kstatic void String_palindrome(int N, int K){ // Fill first K characters with 'a' for (int i = 0; i < K; i++) System.out.print("a"); // Stores a non-palindromic sequence // to be repeated for N - k slots String s = "bcd"; // Print N - k remaining characters for (int i = 0; i < N - K; i++) System.out.print(s.charAt(i % 3));}// Driver Codepublic static void main(String[] args){ // Given N and K int N = 5, K = 3; String_palindrome(N, K);}}// This code is contributed by 29AjayKumar |
Python3
# Python3 program to implement the above approach# Function to generate a string of# length N having longest palindromic# substring of length Kdef string_palindrome(N, K): # Fill first K characters with 'a' for i in range(K): print("a", end = "") # Stores a non-palindromic sequence # to be repeated for N - k slots s = "bcd" # Print N - k remaining characters for i in range(N - K): print(s[i % 3], end = "")# Driver Codeif __name__ == '__main__': # Given N and K N, K = 5, 3 string_palindrome(N, K) # This code is contributed by mohit kumar 29 |
C#
// C# program to implement the above approachusing System;class GFG{ // Function to generate a String of // length N having longest palindromic // subString of length K static void String_palindrome(int N, int K) { // Fill first K characters with 'a' for (int i = 0; i < K; i++) Console.Write("a"); // Stores a non-palindromic sequence // to be repeated for N - k slots string s = "bcd"; // Print N - k remaining characters for (int i = 0; i < N - K; i++) Console.Write(s[i % 3]); } // Driver Code public static void Main(string[] args) { // Given N and K int N = 5, K = 3; String_palindrome(N, K); }}// This code is contributed by AnkThon |
Javascript
<script>// JavaScript program for above approach // Function to generate a String of // length N having longest palindromic // subString of length K function String_palindrome(N, K) { // Fill first K characters with 'a' for (let i = 0; i < K; i++) document.write("a"); // Stores a non-palindromic sequence // to be repeated for N - k slots let s = "bcd"; // Print N - k remaining characters for (let i = 0; i < N - K; i++) document.write(s[i % 3]); }// Driver Code // Given N and K let N = 5, K = 3; String_palindrome(N, K); </script> |
aaabc
Time complexity: O(N)
Auxiliary space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
