DSA-greedy学习

blacsheep

2024-06-03

算法

感觉自己DSA还是不太行, 补一下贪心算法.

316. Remove Duplicate Letters

Given a string s, remove duplicate letters so that every letter appears once and only once. You must make sure your result is the smallest in lexicographical order among all possible results.

Example 1:
    Input: s = "bcabc"
    Output: "abc"

Example 2:
    Input: s = "cbacdcbc"
    Output: "acdb"

greedy + stack

太笨了, 完全想不出来. 这里用了last_occ存了最后出现的位置, 防止字符丢失, 然后用一个stack存字符, 只要stack的最后一个元素后续还有occurance并且stack[-1]比当前大, 我们就直接把stack里面的元素丢掉.

class Solution:
    def removeDuplicateLetters(self, s: str) -> str:
        stack = []
        seen = set()
        last_occ = {c: i for i, c in enumerate(s)}

        for i, c in enumerate(s):
            if c not in seen:
                while stack and c < stack[-1] and i < last_occ[stack[-1]]:
                    seen -= {stack.pop()}
                seen.add(c)
                stack.append(c)
        return ''.join(stack)

难点在于子问题的解决, 即只要不影响最终结果(i < last_occ[stack[-1]]), 我们就可以丢弃stack里的值换更小的value(c < stack[-1]).

55. Jump Game

You are given an integer array nums. You are initially positioned at the array's first index, and each element in the array represents your maximum jump length at that position.

Return true if you can reach the last index, or false otherwise.

Example 1:
    Input: nums = [2,3,1,1,4]
    Output: true
    Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:
    Input: nums = [3,2,1,0,4]
    Output: false
    Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.

dp

第一感觉是dp, 也确实ac了, 但是时间复杂度太高了.

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        dp = [False for i in range(len(nums))]
        dp[-1] = True
        n = len(nums)
        if n == 1:
            return True
        for i in range(n-2, -1, -1):
            v = nums[i]
            for j in range(v+1):
                if i+j < n:
                    if dp[i+j] == True and dp[i]==False:
                        dp[i] = True
                        break
        return dp[0]

greedy

本质思路是直接遍历列表, 对于每个元素, 我们在遍历其大小的时候选择使剩余step最大的方案. 如果某个步骤剩余step到了0, 就说明到不了终点,返回False.

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        count = 0
        for i in nums:
            if count < 0:
                return False
            elif i > count:
                count = i
            count -= 1
        return True

45. Jump Game II

You are given a 0-indexed array of integers nums of length n. You are initially positioned at nums[0].

Each element nums[i] represents the maximum length of a forward jump from index i. In other words, if you are at nums[i], you can jump to any nums[i + j] where:

0 <= j <= nums[i] and i + j < n

Return the minimum number of jumps to reach nums[n - 1]. The test cases are generated such that you can reach nums[n - 1].

Example 1:
    Input: nums = [2,3,1,1,4]
    Output: 2
    Explanation: The minimum number of jumps to reach the last index is 2. Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:
    Input: nums = [2,3,0,1,4]
    Output: 2

greedy

每次跳的区间都划分出来, 实际时间复杂度O(n), 空间复杂度O(1).

class Solution:
    def jump(self, nums: List[int]) -> int:
        prev = None
        curr = 0
        furthest = 0
        n = len(nums)
        ans = 0
        while furthest < n - 1:
            ans += 1
            if prev is None:
                furthest = nums[curr]
            else:
                for i in range(prev+1, curr+1):
                    furthest = max(furthest, i + nums[i])
            prev = curr
            curr = furthest
                
        return ans

409. Longest Palindrome

打卡题

Given a string s which consists of lowercase or uppercase letters, return the length of the longest palindrome that can be built with those letters.

Letters are case sensitive, for example, "Aa" is not considered a palindrome.

Example 1:
    Input: s = "abccccdd"
    Output: 7
    Explanation: One longest palindrome that can be built is "dccaccd", whose length is 7.

Example 2:
    Input: s = "a"
    Output: 1
    Explanation: The longest palindrome that can be built is "a", whose length is 1.

偶数全加,奇数-1然后全加, 最后如果存在奇数就+1

class Solution:
    def longestPalindrome(self, s: str) -> int:
        ctr = Counter(s)
        ans = 0
        exist = 0
        for k, v in ctr.items():
            if v%2:
                ans += v - 1
                exist = 1 
            else:
                ans += v
        return ans + exist

122. Best Time to Buy and Sell Stock II

You are given an integer array prices where prices[i] is the price of a given stock on the ith day.

On each day, you may decide to buy and/or sell the stock. You can only hold at most one share of the stock at any time. However, you can buy it then immediately sell it on the same day.

Find and return the maximum profit you can achieve.

Example 1:
    Input: prices = [7,1,5,3,6,4]
    Output: 7
    Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
    Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.
    Total profit is 4 + 3 = 7.

Example 2:
    Input: prices = [1,2,3,4,5]
    Output: 4
    Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
    Total profit is 4.

Example 3:
    Input: prices = [7,6,4,3,1]
    Output: 0
    Explanation: There is no way to make a positive profit, so we never buy the stock to achieve the maximum profit of 0.

从a到b再从b到c相当于从a到c,所以我们只需要捕捉所有局部增量即可

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        ans = 0
        if len(prices) == 1:
            return 0
        for i in range(len(prices)-1):
            v = prices[i+1] - prices[i]
            if v > 0:
                ans += v 
        return ans

134. Gas Station

There are n gas stations along a circular route, where the amount of gas at the ith station is gas[i].

You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from the ith station to its next (i + 1)th station. You begin the journey with an empty tank at one of the gas stations.

Given two integer arrays gas and cost, return the starting gas station's index if you can travel around the circuit once in the clockwise direction, otherwise return -1. If there exists a solution, it is guaranteed to be unique.

Example 1:
    Input: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
    Output: 3
    Explanation:
    Start at station 3 (index 3) and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
    Travel to station 4. Your tank = 4 - 1 + 5 = 8
    Travel to station 0. Your tank = 8 - 2 + 1 = 7
    Travel to station 1. Your tank = 7 - 3 + 2 = 6
    Travel to station 2. Your tank = 6 - 4 + 3 = 5
    Travel to station 3. The cost is 5. Your gas is just enough to travel back to station 3.
    Therefore, return 3 as the starting index.

Example 2:
    Input: gas = [2,3,4], cost = [3,4,3]
    Output: -1
    Explanation:
    You can't start at station 0 or 1, as there is not enough gas to travel to the next station.
    Let's start at station 2 and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
    Travel to station 0. Your tank = 4 - 3 + 2 = 3
    Travel to station 1. Your tank = 3 - 3 + 3 = 3
    You cannot travel back to station 2, as it requires 4 unit of gas but you only have 3.
    Therefore, you can't travel around the circuit once no matter where you start.

最经典的贪心

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        n = len(gas)
        tank = 0
        if sum(gas) - sum(cost) < 0:
            return -1
        ans = 0
        for i in range(n):
            tank += gas[i] - cost[i]
            if tank > 0 and ans is None:
                ans = i
            if tank < 0:
                tank = 0
                ans = None
        return ans

135. Candy

There are n children standing in a line. Each child is assigned a rating value given in the integer array ratings.

You are giving candies to these children subjected to the following requirements:

Each child must have at least one candy.
Children with a higher rating get more candies than their neighbors.

Return the minimum number of candies you need to have to distribute the candies to the children.

Example 1:
    Input: ratings = [1,0,2]
    Output: 5
    Explanation: You can allocate to the first, second and third child with 2, 1, 2 candies respectively.

Example 2:
    Input: ratings = [1,2,2]
    Output: 4
    Explanation: You can allocate to the first, second and third child with 1, 2, 1 candies respectively.
    The third child gets 1 candy because it satisfies the above two conditions.

思路其实是基于peak和vallay, 初始化所有child的candy为1, 设置一个peak和vallay

递增的时候: peak+1, 糖果加peak

递减的时候: vallay+1, 糖果加vallay

相等的时候糖果依然为1,直接跳过

递增结束或递减结束的时候peak和vallay相应置0

然后每次找到一个趋势变换点都减掉peak和vallay里面的最小值(peak只能取较大值), 遍历到结束即获得所有糖果总数

class Solution:
    def candy(self, ratings: List[int]) -> int:
        n = len(ratings)
        total_candies = n
        i = 1

        while i < n:
            if ratings[i] == ratings[i - 1]:
                i += 1
                continue

            current_peak = 0
            while i < n and ratings[i] > ratings[i - 1]:
                current_peak += 1
                total_candies += current_peak
                i += 1
            
            if i == n:
                return total_candies

            current_valley = 0
            while i < n and ratings[i] < ratings[i - 1]:
                current_valley += 1
                total_candies += current_valley
                i += 1

            total_candies -= min(current_peak, current_valley)

        return total_candies

179. Largest Number

Given a list of non-negative integers nums, arrange them such that they form the largest number and return it.

Since the result may be very large, so you need to return a string instead of an integer.

Example 1:
    Input: nums = [10,2]
    Output: "210"

Example 2:
    Input: nums = [3,30,34,5,9]
    Output: "9534330"

与其说是greedy不如说是sort. 第一次知道sorted里面可以带cmp_to_key这种东西

from functools import cmp_to_key
class Solution:
    def largestNumber(self, nums: List[int]) -> str:
        def mycmp(x, y):
            if x+y > y+x:
                return -1
            elif x == y:
                return 0
            else:
                return 1
        return ''.join(sorted(map(str,nums), key=cmp_to_key(mycmp))).lstrip('0') or '0'

321. Create Maximum Number

You are given two integer arrays nums1 and nums2 of lengths m and n respectively. nums1 and nums2 represent the digits of two numbers. You are also given an integer k.

Create the maximum number of length k <= m + n from digits of the two numbers. The relative order of the digits from the same array must be preserved.

Return an array of the k digits representing the answer.

Example 1:
    Input: nums1 = [3,4,6,5], nums2 = [9,1,2,5,8,3], k = 5
    Output: [9,8,6,5,3]

Example 2:
    Input: nums1 = [6,7], nums2 = [6,0,4], k = 5
    Output: [6,7,6,0,4]

Example 3:
    Input: nums1 = [3,9], nums2 = [8,9], k = 3
    Output: [9,8,9]

个人感觉挺难的一道题, 本质是monostack+merge. 没写出来, 看的别人的solution. 考虑过monostack,但是感觉略微有些区别, 记录一下.

class Solution:
    def maxNumber(self, nums1: List[int], nums2: List[int], k: int) -> List[int]:
        def merge(l1, l2):
            ret = []
            while l1 or l2:
                if l1 > l2:
                    ret.append(l1.pop(0))
                else:
                    ret.append(l2.pop(0))
            return ret
        
        def monostack(lst, length):
            ret = []
            preserve = len(lst) - length
            for i in range(len(lst)):
                while preserve and ret and lst[i] > ret[-1]:
                    ret.pop()
                    preserve -= 1
                ret.append(lst[i])
            return ret[:length]
        
        n1 = len(nums1)
        n2 = len(nums2)
        res = []
        for i in range(k+1):
            j = k-i
            if i <= n1 and j <= n2:
                lst1 = monostack(nums1, i)
                lst2 = monostack(nums2, j)
                res = max(res, merge(lst1, lst2))
        return res

846. Hand of Straights

Alice has some number of cards and she wants to rearrange the cards into groups so that each group is of size groupSize, and consists of groupSize consecutive cards.

Given an integer array hand where hand[i] is the value written on the ith card and an integer groupSize, return true if she can rearrange the cards, or false otherwise.

Example 1:
    Input: hand = [1,2,3,6,2,3,4,7,8], groupSize = 3
    Output: true
    Explanation: Alice's hand can be rearranged as [1,2,3],[2,3,4],[6,7,8]

Example 2:
    Input: hand = [1,2,3,4,5], groupSize = 4
    Output: false
    Explanation: Alice's hand can not be rearranged into groups of 4.

直观解法

class Solution:
    def isNStraightHand(self, hand: List[int], groupSize: int) -> bool:
        if len(hand) % groupSize:
            return False
        hand = sorted(hand)
        lst = []
        for i in hand:
            if lst and lst[-1][0] == i:
                lst[-1][1] += 1
            else:
                lst.append([i, 1])
        while len(lst)>=groupSize:
            k, v = lst.pop(0)
            if v > 0:
                prev = k
                for j in range(groupSize-1):
                    if lst[j][0] != prev + 1:
                        return False
                    prev = prev+1
                    lst[j][1] -= v
                    if lst[j][1] < 0:
                        return False

        while lst:
            k, v = lst.pop(0)
            if v > 0:
                return False
        return True

优化的版本, 用双向列表, 手牌先排序, 然后尽可能得叠顺子, 如果最小数都不能连接下一张牌就说明不满足.

class Solution:
    def isNStraightHand(self, hand: List[int], groupSize: int) -> bool:
        hand.sort()
        lst = []
        for card in hand:
            if not lst:
                item = [1, card]
            else:
                if card == lst[0][1] + 1:
                    item = lst.pop(0)
                    item[0] += 1
                    item[1] = card
                elif card == lst[0][1]:
                    item = [1, card]
                else:
                    return False
            
            if item[0] < groupSize:
                lst.append(item)
            
        return len(lst) == 0

330. Patching Array

Given a sorted integer array nums and an integer n, add/patch elements to the array such that any number in the range [1, n] inclusive can be formed by the sum of some elements in the array.

Return the minimum number of patches required.

Example 1:
    Input: nums = [1,3], n = 6
    Output: 1
    Explanation:
    Combinations of nums are [1], [3], [1,3], which form possible sums of: 1, 3, 4.
    Now if we add/patch 2 to nums, the combinations are: [1], [2], [3], [1,3], [2,3], [1,2,3].
    Possible sums are 1, 2, 3, 4, 5, 6, which now covers the range [1, 6].
    So we only need 1 patch.

Example 2:
    Input: nums = [1,5,10], n = 20
    Output: 2
    Explanation: The two patches can be [2, 4].

Example 3:
    Input: nums = [1,2,2], n = 5
    Output: 0

有点复杂, 没写出来, 感觉是纯数学.

对于我们可以得到的[0, x], 假设我们得不到x+1, 那么我们就把x+1加进来, 这样我们就可以获取[0, 2x+1]的所有值, 即case2

对于所有的nums里面的值, 如果 x < nums[i] < 2x + 1, 在我们获取到 [x, 2x+1]之后, nums[i]也可以加进来, 从而我们可以获得[0, 2x+1 + nums[i]]. 即case1

class Solution:
    def minPatches(self, nums: List[int], n: int) -> int:
        i = 0
        bound = 0
        ans = 0
        while bound < n:
            if i < len(nums) and nums[i] <= bound + 1:
                bound += nums[i]
                i += 1
            else:
                ans += 1
                bound += bound + 1

        return ans

334. Increasing Triplet Subsequence

Given an integer array nums, return true if there exists a triple of indices (i, j, k) such that i < j < k and nums[i] < nums[j] < nums[k]. If no such indices exists, return false.

Example 1:
    Input: nums = [1,2,3,4,5]
    Output: true
    Explanation: Any triplet where i < j < k is valid.

Example 2:
    Input: nums = [5,4,3,2,1]
    Output: false
    Explanation: No triplet exists.

Example 3:
    Input: nums = [2,1,5,0,4,6]
    Output: true
    Explanation: The triplet (3, 4, 5) is valid because nums[3] == 0 < nums[4] == 4 < nums[5] = 6.

最长递增子串, 做过一次

class Solution:
    def increasingTriplet(self, nums: List[int]) -> bool:
        stack = []
        for i in nums:
            if not stack:
                stack.append(i)
            else:
                if i > stack[-1]:
                    stack.append(i)
                    if len(stack) == 3:
                        return True
                else:
                    stack[bisect.bisect_left(stack, i)] = i
        return len(stack) >= 3

存在优化, 因为只需要三个元素, 逻辑并不需要二分, 直接判断即可.

class Solution:
    def increasingTriplet(self, nums: List[int]) -> bool:
        first = second = math.inf
        for i in nums:
            if i <= first:
                first = i
            elif i <= second:
                second = i
            else:
                return True
        return False

376. Wiggle Subsequence

A wiggle sequence is a sequence where the differences between successive numbers strictly alternate between positive and negative. The first difference (if one exists) may be either positive or negative. A sequence with one element and a sequence with two non-equal elements are trivially wiggle sequences.

For example, [1, 7, 4, 9, 2, 5] is a wiggle sequence because the differences (6, -3, 5, -7, 3) alternate between positive and negative. In contrast, [1, 4, 7, 2, 5] and [1, 7, 4, 5, 5] are not wiggle sequences. The first is not because its first two differences are positive, and the second is not because its last difference is zero. A subsequence is obtained by deleting some elements (possibly zero) from the original sequence, leaving the remaining elements in their original order.

Given an integer array nums, return the length of the longest wiggle subsequence of nums.

Example 1:
    Input: nums = [1,7,4,9,2,5]
    Output: 6
    Explanation: The entire sequence is a wiggle sequence with differences (6, -3, 5, -7, 3).

Example 2:
    Input: nums = [1,17,5,10,13,15,10,5,16,8]
    Output: 7
    Explanation: There are several subsequences that achieve this length.
    One is [1, 17, 10, 13, 10, 16, 8] with differences (16, -7, 3, -3, 6, -8).

Example 3:
    Input: nums = [1,2,3,4,5,6,7,8,9]
    Output: 2

stack思路

class Solution:
    def wiggleMaxLength(self, nums: List[int]) -> int:
        stack = []
        state = None
        for i in nums:
            if not stack:
                stack.append(i)
            else:
                if i == stack[-1]:
                    continue
                elif (state is None or state is True) and i < stack[-1]:
                    stack.append(i)
                    state = False
                elif (state is None or state is False) and i > stack[-1]:
                    stack.append(i)
                    state = True
                else:
                    stack.pop()
                    stack.append(i)
        return len(stack)

实际中间变量可以无视, 贪心思路

class Solution:
    def wiggleMaxLength(self, nums: List[int]) -> int:
        n = len(nums)
        if n < 2:
            return n
        
        ans = 1
        prev = None
        for i in range(1, n):
            diff = nums[i] - nums[i-1]
            if (diff > 0 and prev != 1) or (diff < 0 and prev != -1):
                ans += 1
                prev = 1 if diff > 0 else -1
        return ans

397. Integer Replacement

Given a positive integer n, you can apply one of the following operations:

If n is even, replace n with n / 2.
If n is odd, replace n with either n + 1 or n - 1.

Return the minimum number of operations needed for n to become 1.

Example 1:
    Input: n = 8
    Output: 3
    Explanation: 8 -> 4 -> 2 -> 1

Example 2:
    Input: n = 7
    Output: 4
    Explanation: 7 -> 8 -> 4 -> 2 -> 1
    or 7 -> 6 -> 3 -> 2 -> 1

Example 3:
    Input: n = 4
    Output: 2

看二进制末两位, 最后俩二进制位为11且数字大于3我们选择加, 其他时候选择减

class Solution:
    def integerReplacement(self, n: int) -> int:
        ans = 0
        while n != 1:
            if n & 1:
                if n & 2 and n > 3:
                    n += 1
                    n >>= 2
                    ans += 3
                else:
                    n -= 1
                    n >>= 1
                    ans += 2
            else:
                n >>= 1
                ans += 1
        return ans

402. Remove K Digits

Given string num representing a non-negative integer num, and an integer k, return the smallest possible integer after removing k digits from num.

Example 1:
    Input: num = "1432219", k = 3
    Output: "1219"
    Explanation: Remove the three digits 4, 3, and 2 to form the new number 1219 which is the smallest.

Example 2:
    Input: num = "10200", k = 1
    Output: "200"
    Explanation: Remove the leading 1 and the number is 200. Note that the output must not contain leading zeroes.

Example 3:
    Input: num = "10", k = 2
    Output: "0"
    Explanation: Remove all the digits from the number and it is left with nothing which is 0.

monostack, stack存数值, 一旦检测更小值就pop然后k-=1, 直到符合要求.

class Solution:
    def removeKdigits(self, num: str, k: int) -> str:
        n = len(num)
        if num.count('0') >= n-k:
            return '0'
        stack = []
        for i in num:
            while k and stack and stack[-1] > i:
                stack.pop()
                k -= 1
            stack.append(i)

        return ''.join(stack[:-k or None]).lstrip('0')

502. IPO

描述复杂, 简单说就是给出两个list: profits和capital. 分别对应一个项目列表的纯利润和最低启动资金

需要求解在拥有w的启动资金且最多做k个项目的情况下的最大利润

Example 1:
    Input: k = 2, w = 0, profits = [1,2,3], capital = [0,1,1]
    Output: 4
    Explanation: Since your initial capital is 0, you can only start the project indexed 0.
    After finishing it you will obtain profit 1 and your capital becomes 1.
    With capital 1, you can either start the project indexed 1 or the project indexed 2.
    Since you can choose at most 2 projects, you need to finish the project indexed 2 to get the maximum capital.
    Therefore, output the final maximized capital, which is 0 + 1 + 3 = 4.

Example 2:
    Input: k = 3, w = 0, profits = [1,2,3], capital = [0,1,2]
    Output: 6

一开始的做法有点暴力, 但也能AC

class Solution:
    def findMaximizedCapital(self, k: int, w: int, profits: List[int], capital: List[int]) -> int:
        d = defaultdict(list)
        for k_, v_ in sorted(zip(profits, capital), key=lambda x: (-x[0], x[1])):
            d[k_].append(v_)

        curr_capital = w
        chosen_k = None
        chosen_v = None
        while k:
            for k_, v_ in d.items():
                if v_[0] <= curr_capital:
                    chosen_k = k_
                    chosen_v = v_[0]
                    break

            if chosen_v is None:
                break
            curr_capital += chosen_k
            if len(d[chosen_k]) == 1:
                d.pop(chosen_k)
            else:
                d[chosen_k].pop(0)
            chosen_k = None
            chosen_v = None
            k -= 1
        return curr_capital

更简单的思路是zip之后按capital进行sort, 然后每一个符合条件的都丢优先队列, 资金不足以启动的时候挑一个最大利润的项目做, 然后继续丢优先队列, 最后 heapq.heappop 按需取出即可.

class Solution:
    def findMaximizedCapital(self, k: int, w: int, profits: List[int], capital: List[int]) -> int:
        sorted_data = sorted(zip(capital, profits))
        queue = []
        i = 0
        n = len(profits)
        while k:
            while i < n and sorted_data[i][0] <= w:
                heapq.heappush(queue, -sorted_data[i][1])
                i += 1
            if not queue:
                break
            w -= heapq.heappop(queue)
            k -= 1
        return w

2193. Minimum Number of Moves to Make Palindrome

You are given a string s consisting only of lowercase English letters.

In one move, you can select any two adjacent characters of s and swap them.

Return the minimum number of moves needed to make s a palindrome.

Note that the input will be generated such that s can always be converted to a palindrome.

Example 1:
    Input: s = "aabb"
    Output: 2
    Explanation:
    We can obtain two palindromes from s, "abba" and "baab". 
    - We can obtain "abba" from s in 2 moves: "aabb" -> "abab" -> "abba".
    - We can obtain "baab" from s in 2 moves: "aabb" -> "abab" -> "baab".
    Thus, the minimum number of moves needed to make s a palindrome is 2.

Example 2:
    Input: s = "letelt"
    Output: 2
    Explanation:
    One of the palindromes we can obtain from s in 2 moves is "lettel".
    One of the ways we can obtain it is "letelt" -> "letetl" -> "lettel".
    Other palindromes such as "tleelt" can also be obtained in 2 moves.
    It can be shown that it is not possible to obtain a palindrome in less than 2 moves.

感觉是贪心但是一开始证明不出来, 只能证明每次去除掉最优解的最左最右不影响内部结构, 所以可以迭代求解.

class Solution:
    def minMovesToMakePalindrome(self, s: str) -> int:
        if s == s[::-1]:
            return 0
        d = defaultdict(list)
        for idx, char in enumerate(s):
            if len(d[char]) < 2:
                d[char].append(idx)
            else:
                d[char][1] = idx
        first = None
        last = None
        n = len(s)
        min_step = float('inf')
        for k, v in d.items():
            if len(v) == 2 and (n - 1 - v[1]) + (v[0]) < min_step:
                first = v[0]
                last = v[-1]
                min_step = (n - 1 - last) + first
        return min_step + self.minMovesToMakePalindrome(s[:first]+s[first+1:last]+s[last+1:])

不可思议的是居然可以AC. 最优解是贪心, 只需要找最左匹配和最右匹配然后比较即可.

c++ 2 pointers with detail proof and explanation

class Solution:
    def minMovesToMakePalindrome(self, s: str) -> int:
        ans = 0 
        while len(s) > 2: 
            lo = s.find(s[-1])
            hi = s.rfind(s[0])
            if lo < len(s)-hi-1: 
                ans += lo 
                s = s[:lo] + s[lo+1:-1]
            else: 
                ans += len(s)-hi-1
                s = s[1:hi] + s[hi+1:]
        return ans