Longest Palindromic Substring with Transformations
Medium
Java
Collections
27 views
Problem Statement
Given a string and a maximum number of allowed character transformations, find the longest palindromic substring that can be formed by transforming at most k characters. A transformation means changing any character to any other character.
Input Format
A string S
An integer k (maximum allowed character transformations)
An integer k (maximum allowed character transformations)
Output Format
Length of the longest palindromic substring that can be formed using at most k transformations.
Example
abcde 1
3
Constraints
• 1 ≤ length of S
• 0 ≤ k
• Characters are case-sensitive
• Transformation = change one character to any other character
• 0 ≤ k
• Characters are case-sensitive
• Transformation = change one character to any other character
Concept Explanation
A palindrome reads the same from left to right and right to left.
We are allowed to change at most k characters to make a substring a palindrome.
Example:
For "abcde" and k = 1
• Substring "abc" → change a to c → "cbc" (palindrome, length 3)
We are allowed to change at most k characters to make a substring a palindrome.
Example:
For "abcde" and k = 1
• Substring "abc" → change a to c → "cbc" (palindrome, length 3)
Step-by-Step Explanation
1.Take input string S and integer k.
2.Initialize maxLength = 1.
3.For each index i in the string:
• Treat i as center of palindrome (odd length).
• Also treat (i, i+1) as center (even length).
4.For each center:
• Set left and right pointers.
• Initialize changes = 0.
5.While left >= 0 and right < length:
• If S[left] != S[right], increment changes.
• If changes > k, stop expanding.
• Update maxLength with (right - left + 1).
• Move left-- and right++.
6.Repeat for all centers.
7.Return maxLength.
2.Initialize maxLength = 1.
3.For each index i in the string:
• Treat i as center of palindrome (odd length).
• Also treat (i, i+1) as center (even length).
4.For each center:
• Set left and right pointers.
• Initialize changes = 0.
5.While left >= 0 and right < length:
• If S[left] != S[right], increment changes.
• If changes > k, stop expanding.
• Update maxLength with (right - left + 1).
• Move left-- and right++.
6.Repeat for all centers.
7.Return maxLength.
Concept Explanation
A palindrome reads the same from left to right and right to left.
We are allowed to change at most k characters to make a substring a palindrome.
Example:
For "abcde" and k = 1
• Substring "abc" → change a to c → "cbc" (palindrome, length 3)
We are allowed to change at most k characters to make a substring a palindrome.
Example:
For "abcde" and k = 1
• Substring "abc" → change a to c → "cbc" (palindrome, length 3)
Step-by-Step Explanation
1.Take input string S and integer k.
2.Initialize maxLength = 1.
3.For each index i in the string:
• Treat i as center of palindrome (odd length).
• Also treat (i, i+1) as center (even length).
4.For each center:
• Set left and right pointers.
• Initialize changes = 0.
5.While left >= 0 and right < length:
• If S[left] != S[right], increment changes.
• If changes > k, stop expanding.
• Update maxLength with (right - left + 1).
• Move left-- and right++.
6.Repeat for all centers.
7.Return maxLength.
2.Initialize maxLength = 1.
3.For each index i in the string:
• Treat i as center of palindrome (odd length).
• Also treat (i, i+1) as center (even length).
4.For each center:
• Set left and right pointers.
• Initialize changes = 0.
5.While left >= 0 and right < length:
• If S[left] != S[right], increment changes.
• If changes > k, stop expanding.
• Update maxLength with (right - left + 1).
• Move left-- and right++.
6.Repeat for all centers.
7.Return maxLength.
Input / Output Format
Input Format
A string S
An integer k (maximum allowed character transformations)
An integer k (maximum allowed character transformations)
Output Format
Length of the longest palindromic substring that can be formed using at most k transformations.
Constraints
• 1 ≤ length of S
• 0 ≤ k
• Characters are case-sensitive
• Transformation = change one character to any other character
• 0 ≤ k
• Characters are case-sensitive
• Transformation = change one character to any other character
Examples
Input:
abcde
1
Output:
3
Example Solution (Public)
import java.util.*;
public class LongestPalindromicSubstring {
public static String longestPalindromeWithKTransformations(String s, int k) {
int n = s.length();
if (n == 0) return "";
if (n == 1) return s;
String result = "";
int maxLength = 0;
// Try every possible center for palindrome
for (int center = 0; center < n; center++) {
// Check for odd length palindromes
String oddPal = expandAroundCenter(s, center, center, k);
if (oddPal.length() > maxLength ||
(oddPal.length() == maxLength && oddPal.compareTo(result) < 0)) {
maxLength = oddPal.length();
result = oddPal;
}
// Check for even length palindromes
String evenPal = expandAroundCenter(s, center, center + 1, k);
if (evenPal.length() > maxLength ||
(evenPal.length() == maxLength && evenPal.compareTo(result) < 0)) {
maxLength = evenPal.length();
result = evenPal;
}
}
return result;
}
private static String expandAroundCenter(String s, int left, int right, int k) {
int n = s.length();
int transformationsNeeded = 0;
int bestLeft = left;
int bestRight = right;
// Expand as much as possible within k transformations
while (left >= 0 && right < n) {
if (s.charAt(left) != s.charAt(right)) {
transformationsNeeded++;
}
if (transformationsNeeded > k) {
break;
}
bestLeft = left;
bestRight = right;
left--;
right++;
}
// Build the palindrome string
StringBuilder palindrome = new StringBuilder();
for (int i = bestLeft; i <= bestRight; i++) {
// Use the character that appears more frequently in the symmetric positions
char leftChar = s.charAt(bestLeft + (bestRight - i));
char rightChar = s.charAt(i);
if (leftChar == rightChar) {
palindrome.append(leftChar);
} else {
// Choose lexicographically smaller character
palindrome.append((leftChar < rightChar) ? leftChar : rightChar);
}
}
return palindrome.toString();
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String s = scanner.nextLine();
int k = scanner.nextInt();
String result = longestPalindromeWithKTransformations(s, k);
System.out.println(result);
scanner.close();
}
}
Official Solution Code
import java.util.*;
public class LongestPalindromicSubstring {
public static String longestPalindromeWithKTransformations(String s, int k) {
int n = s.length();
if (n == 0) return "";
if (n == 1) return s;
String result = "";
int maxLength = 0;
// Try every possible center for palindrome
for (int center = 0; center < n; center++) {
// Check for odd length palindromes
String oddPal = expandAroundCenter(s, center, center, k);
if (oddPal.length() > maxLength ||
(oddPal.length() == maxLength && oddPal.compareTo(result) < 0)) {
maxLength = oddPal.length();
result = oddPal;
}
// Check for even length palindromes
String evenPal = expandAroundCenter(s, center, center + 1, k);
if (evenPal.length() > maxLength ||
(evenPal.length() == maxLength && evenPal.compareTo(result) < 0)) {
maxLength = evenPal.length();
result = evenPal;
}
}
return result;
}
private static String expandAroundCenter(String s, int left, int right, int k) {
int n = s.length();
int transformationsNeeded = 0;
int bestLeft = left;
int bestRight = right;
// Expand as much as possible within k transformations
while (left >= 0 && right < n) {
if (s.charAt(left) != s.charAt(right)) {
transformationsNeeded++;
}
if (transformationsNeeded > k) {
break;
}
bestLeft = left;
bestRight = right;
left--;
right++;
}
// Build the palindrome string
StringBuilder palindrome = new StringBuilder();
for (int i = bestLeft; i <= bestRight; i++) {
// Use the character that appears more frequently in the symmetric positions
char leftChar = s.charAt(bestLeft + (bestRight - i));
char rightChar = s.charAt(i);
if (leftChar == rightChar) {
palindrome.append(leftChar);
} else {
// Choose lexicographically smaller character
palindrome.append((leftChar < rightChar) ? leftChar : rightChar);
}
}
return palindrome.toString();
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String s = scanner.nextLine();
int k = scanner.nextInt();
String result = longestPalindromeWithKTransformations(s, k);
System.out.println(result);
scanner.close();
}
}
Please login to submit solutions.