2002. Maximum Product of the Length of Two Palindromic Subsequences

2002. Maximum Product of the Length of Two Palindromic Subsequences

https://leetcode.com/problems/maximum-product-of-the-length-of-two-palindromic-subsequences/

문제

풀이(비트 마스크)

비트 마스크를 통해 모든 경우의 수를 비트로 표현할 수 있다.
예를 들어서 s = "etea"라고 한다면 비트로 표현된 것은 다음과 같다.

즉 비트에서 1이면 해당 인덱스 문자가 있는 것이고 0이면 문자가 없는 것이다. 이렇게 모든 경우를 나타낼 수 있다.
이렇게 모든 경우를 구했으면 여기서 팔린드롬인 것을 찾는다.

즉 숫자 1일 때 "a", 2일 때 = "e", 4일 때 = "t" ..... 14일 때 "ete"라는 것을 알았으면 이 조합을 딕셔너리에 넣는다.
dp[1] = len("a")
dp[2] = len("b")
dp[4] = len("t")
dp[8] = len("e")
dp[10] = len("ee")
dp[14] = len("ete")가 될 것이다. 마지막으로 겹치지 않는 것을 찾아야 한다.
그 방법은 &연산으로 해결할 수 있는데 예를 들어서
8 & 10을 하게되면 8이 나오고 이것은 겹쳐진다고 볼 수 있다. 반면에
1 & 14를 하게되면 1이 겹치는 것이 없으므로 0이 나온다.
이렇게 &연산을 통해 해결한다.

<<은 쉬프트 연산으로 1 << N을 하게되면 모든 경우의 개수를 구할 수 있다. 예를 들어서 s = "etea"할 때 N = 4가 되고 1<<N은 곧 (10000) 16이라고 볼 수 있다.
mask마다 1이 포함되어 있는 것을 확인할 때에는 (1 << i)로 해결한다.

결과(비트 마스크)