Longest Palindromic Substring with Transformations
Java
Medium
1 views
Problem Description
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
- First line: String s (1 ≤ |s| ≤ 1000) containing lowercase English letters
- Second line: Integer k (0 ≤ k ≤ |s|) representing maximum allowed transformations
Output Format
- Single line: The longest palindromic substring that can be formed
- If multiple palindromes of same maximum length exist, return the lexicographically smallest one
- If no palindrome can be formed, return ""
Constraints
- Time complexity: O(n²) or better
- Space complexity: O(n²) or better
- Handle edge cases like single character strings
- Handle cases where k = 0 (must find existing palindrome)
Official Solution
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();
}
}
Solutions (0)
No solutions submitted yet. Be the first!
No comments yet. Start the discussion!