LC: 1216. Valid Palindrome III
https://leetcode.com/problems/valid-palindrome-iii/
1216. Valid Palindrome III
Given a string s and an integer k, return true if s is a k-palindrome.
A string is k-palindrome if it can be transformed into a palindrome by removing at most k characters from it.
Example 1:
Input: s = "abcdeca", k = 2
Output: true
Explanation: Remove 'b' and 'e' characters.Example 2:
Input: s = "abbababa", k = 1
Output: trueConstraints:
1 <= s.length <= 1000sconsists of only lowercase English letters.1 <= k <= s.length
The Essence:
Hier suchen wir eigentlich die längste palindromische Teilfolge des Strings, die nicht unbedingt zusammenhängend ist, da man Zeichen inzwischen auch löschen kann.
Details:
Dieses Problem lässt sich durch Anwendung der dynamischen Programmierıung lösen. Wenn zwei Zeichen i und j das gleiche Zeichen haben und zwischen diesen es eine palindromische Teilfolge gibt, dann gibt es jetzt eine neue palindromische Folge mit der Länge der Vorherigen Folge plus 2.
Default Code:
Last updated