1542. Find Longest Awesome Substring

[zeikar]

Problem link

https://leetcode.com/problems/find-longest-awesome-substring/

Problem Summary

swap을 해서 팰린드롬이 될 수 있으면 awesome이라고 할 때, 주어진 문자열의 substring 중 가장 긴 awesome 부분 문자열의 길이를 구하는 문제.

Solution

일단 swap해서 팰린드롬이 되려면 문자의 수가 전부 짝수이거나 하나만 홀수이어야 한다. 그러면 각 문자가 나온 수를 카운트 해줘야 하는데... 이건 XOR 연산으로 해주면 된다.

각 문자의 카운트가 나온 최소 인덱스를 dp 배열에 담아두고 같은 카운트가 되면 길이를 구해서 갱신해주면 된다.

Source Code

class Solution:
    def longestAwesome(self, s: str) -> int:
        dp = [len(s)] * 1024
        dp[0] = -1

        cnt = 0
        ans = 0

        for i in range(len(s)):
            num = int(s[i])
            cnt = cnt ^ (1 << num)
            ans = max(ans, i - dp[cnt])

            for j in range(10):
                ans = max(ans, i - dp[cnt ^ (1 << j)])

            dp[cnt] = min(dp[cnt], i)

        return ans