Python으로 부분 문자열이 회문이 될 수 있는지 판별하는 방법

문제 개요

문자열 s가 주어지면, 이 문자열의 부분 문자열에 대해 여러 개의 쿼리를 수행해야 합니다. 각 쿼리 queries[i]는 [left, right, k]의 세 요소로 구성되며, 부분 문자열 s[left] ~ s[right]를 자유롭게 재배열한 뒤, 최대 k개의 문자를 원하는 소문자 영어 알파벳으로 교체할 수 있습니다. 이러한 연산을 거친 후 해당 부분 문자열이 회문(palindrome)이 될 수 있다면 쿼리의 결과는 true, 그렇지 않다면 false입니다. 모든 쿼리의 결과를 순서대로 담은 배열 answer[]를 구하는 것이 목표이며, answer[i]는 i번째 쿼리의 결과여야 합니다.

예를 들어 입력 문자열이 "abcda"이고, 쿼리가 [[3,3,0],[1,2,0],[0,3,1],[0,3,2],[0,4,1]]이라면 출력은 [true, false, false, true, true]가 됩니다.

핵심 아이디어: 홀수 빈도 문자 세기

회문이 성립하려면 각 문자의 등장 횟수가 대부분 짝수여야 하고, 가운데에 배치될 딱 한 문자만 홀수 번 등장할 수 있습니다. 즉, 등장 횟수가 홀수인 서로 다른 문자의 개수가 최대 1개여야 한다는 것이 회문의 필수 조건입니다.

문자 재배열에는 제약이 없으므로, 실제로 확인해야 할 것은 쿼리 구간 안에서 홀수 번 등장하는 문자의 개수뿐입니다. 또한 교체 연산 한 번은 홀수 개인 두 문자를 동시에 짝수로 만들 수 있습니다. 홀수 개인 문자 하나를 다른 홀수 개인 문자와 같은 글자로 바꾸면 두 문자 모두 짝수 개가 되기 때문입니다. 따라서 홀수 빈도 문자의 수를 one이라 할 때, one // 2 <= k를 만족하면 해당 구간을 회문으로 만들 수 있습니다.

쿼리마다 구간을 직접 순회하면 비효율적이므로, 미리 누적 빈도 테이블(dp)을 구성해 둡니다. dp[i][j]는 문자열 앞에서 i번째 위치까지 알파벳 j가 등장한 횟수를 저장하며, 이를 통해 임의 구간의 문자별 개수를 O(26) 시간에 계산할 수 있습니다.

풀이 단계

solve 메서드를 정의합니다. dp 행렬과 쿼리 q를 받아 다음과 같이 동작합니다.
l := q[0], r := q[1], k := q[2]로 설정한 뒤, l과 r을 각각 1 증가시키고 one := 0으로 초기화합니다.
i를 0부터 25까지 반복하며 one := one + (dp[r][i] − dp[l−1][i]) mod 2를 누적합니다. 이 값이 구간 내에서 홀수 번 등장하는 알파벳의 개수입니다.
one // 2 <= k이면 true를, 아니면 false를 반환합니다.
make_dp 메서드를 정의합니다. dp 행렬과 문자열 s를 받아 누적 빈도를 채웁니다.
i를 1부터 len(s)까지 반복하면서, 각 i마다 j를 0부터 25까지 순회해 dp[i][j] := dp[i−1][j]를 복사하고, 이후 dp[i][ord(s[i]) − ord('a')] 값을 1 증가시킵니다.

메인 로직

n := 문자열 s의 길이로 설정하고, s 앞에 공백 한 칸을 붙여 1-based 인덱싱에 맞춥니다.
(n + 1) × 26 크기의 0으로 채워진 dp 행렬을 생성합니다.
make_dp(dp, s)를 호출해 누적 빈도 테이블을 완성합니다.
쿼리 개수와 같은 크기의 res 배열을 false로 초기화합니다.
각 쿼리에 대해 res[i] := solve(dp, q[i])를 수행합니다.
res를 반환합니다.

복잡도 분석: 전처리에 O(n × 26), 각 쿼리 처리에 O(26)이 소요되므로 전체 시간 복잡도는 O((n + q) × 26)이며, 공간 복잡도는 O(n × 26)입니다. 매 쿼리마다 부분 문자열을 새로 세는 O(n × q) 방식보다 훨씬 효율적입니다.

예제 코드 (Python)

다음 구현을 통해 더 잘 이해해 보겠습니다.

class Solution(object):
   def solve(self,dp,q):
      l = q[0]
      r = q[1]
      k = q[2]
      r+=1
      l+=1
      #arr = [ 0 for i in range(26)]
      one = 0
      for i in range(26):
         one += (dp[r][i]-dp[l-1][i])%2
      return one//2<=k
   def make_dp(self,dp,s):
      for i in range(1,len(s)):
         for j in range(26):
            dp[i][j] = dp[i-1][j]
         dp[i][ord(s[i])-ord('a')]+=1
   def canMakePaliQueries(self, s, q):
      n = len(s)
      s = " "+s
      dp = [[0 for i in range(26)] for j in range(n+1)]
      self.make_dp(dp,s)
      res = [False for i in range(len(q))]
      for i in range(len(q)):
         res[i] = self.solve(dp,q[i])
      return res
ob = Solution()
print(ob.canMakePaliQueries("abcda", [[3,3,0],[1,2,0],[0,3,1],[0,3,2],[0,4,1]]))

입력

"abcda"
[[3,3,0],[1,2,0],[0,3,1],[0,3,2],[0,4,1]]

출력

[True, False, False, True, True]