[leetcode] 1328. Break a Palindrome

문제 : https://leetcode.com/problems/break-a-palindrome/

---

소문자 영어로 이루어진 펠린드롬 문자열이 주어지면 한 문자만 다른 소문자 알파벳으로 변경하여 펠린드롬이 아닌 문자열로 만들고자 한다. 이 때, 사전순으로 가장 작은 문자열을 구하라. 만일 조건을 만족하는 변경 가능한 문자열이 없는 경우 빈 문자열을 반환하라.

---

펠린드롬이므로 1/2 개만 탐색해도 된다. (앞뒤 문자가 같으므로)

문자열이 홀수인 경우 가운데 문자는 펠린드롬 여부와 관계가 없으므로 변경하는 문자에서 제외시켜야 한다.

 -> 문자열 길이가 1인 경우 빈문자열을 반환한다. (어떤 문자를 바꿔도 펠린드롬이 되므로)

앞에서 1/2개의 문자들 중 ‘a’가 아닌 문자가 있으면 이를  ‘a’로 바꾼다. (앞에 문자가 작을수록 사전순으로 작기 때문에)

만일 탐색하는 모든 문자들이 ‘a’인 경우 마지막 알파벳을 ‘b’로 바꿔준다. (문자를 감소시키지 않고 증가시키는 경우 가장 뒤에 있는 알파벳을 증가시키는게 사전순으로 작기 때문에)

 

시간복잡도는 문자열 길이를 N이라 했을 때, O(N/2).

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/1328.%20Break%20a%20Palindrome.cpp