HackerRank Interview Preparation Kit > String Manipulation

HackerRank의 Interview Preparation Kit > String Manipulation의 Medium 이상 문제

Sherlock and Valid String - medium

문제요약

입력 string s의 각 문자의 개수가 동일하거나 문자 하나만 제거해서 모두 동일해지면 'YES'아니면 'NO' 리턴 (1<=|s|<=10^5)

Sample Input

aabbcd

Sample output

NO

풀이

각 문자의 개수를 센다음 위 조건이 맞는지 판단

Special Palindrome Again - medium

문제요약

입력 string의 substring 중 palindromic string의 갯수(1<=|s|<=10^6)

palindromic string : 전체가 모두 같은 글자, 가운데 글자를 제외하고 모두 같은 글자

Sample Input

5

asasd

Sample output

7

풀이

처음엔 홀수인 경우와 짝수인 경우를 나눠서 일일이 계산

하지만 문자 갯수를 세면 좀 더 빠르게 구할 수 있다. 예로 aabaa 인 경우 a=2 b=1 a=2가 되고 모두 같은 경우는 길이가 n일 때 n*(n+1)/2가 된다. 즉 3+1+3=7(a, a, aa, b, a, a, aa) 가운데만 다른 경우는 갯수가 1인 문자의 양쪽 문자가 같은 경우 더 짧은 길이 만큼이 된다. b=1이고 양쪽다 a이므로 2(aba, aabaa). 둘을 더해주면 전체 palindromic string의 갯수가 나온다. (discussions을 보고 알았다...)

Common Child - medium

문제요약

두 string에서 각각 0개 이상의 문자를 지웠을 때 서로 같아지는 string의 최대 길이 계산

LCS(최장 공통 부분 수열) 문제

Sample Input

HARRY

SALLY

Sample output

2

풀이

discussion을 보고 이해했다. 알고리즘에서는 고전에 속하는 내용인 듯 하다.

주어진 두 문자열(s1, s2)에서 일부를 지웠을 때의 최장 공통 부분 수열을 계산한다. 자세한 설명은 최장 공통 부분 수열을 참고하면 이해하기 쉽다. 결국 DP 문제로 어떤 위치(s1[i],s2[j]) 까지의 최장 공통 부분 수열을 고려할 때, s1[i] == s2[j]라면 LCS(s1[i], s2[j])는 LCS(s1[i-1], s2[j-1])+s1[i]와 같다. 만약 s1[i] != s2[j]라면 LCS(s1[i], s2[j])는 max(LCS(s1[i-1],s2[j]), LCS(s1[i], s2[j-1]))과 같다. 길이가 0인 경우는 빈 문자열이 되고, s1 * s2 배열에서 위 조건에 맞게 계산을 하면 마지막 계산된 값이 두 문자열의 LCS가 된다.

알고리즘을 알고 나면 구현은 어렵지 않은 문제로, 두 문자열의 길이를 n,m이라고 하면 O(n+m)의 시간과 공간을 사용한다. python3에서는 time out이 발생하고, pypy3로 pass된다.

비슷한 문제로 최장 공통 부분 문자열도 있다.