[LeetCode] 1328. Break a Palindrome

1328. Break a Palindrome

Medium

Given a palindromic string of lowercase English letters palindrome, replace exactly one character with any lowercase English letter so that the resulting string is not a palindrome and that it is the lexicographically smallest one possible.

Return the resulting string. If there is no way to replace a character to make it not a palindrome, return an empty string.

A string a is lexicographically smaller than a string b (of the same length) if in the first position where a and b differ, a has a character strictly smaller than the corresponding character in b. For example, "abcc" is lexicographically smaller than "abcd" because the first position they differ is at the fourth character, and 'c' is smaller than 'd'.

 

Example 1:

Input: palindrome = "abccba"
Output: "aaccba"
Explanation: There are many ways to make "abccba" not a palindrome, such as "zbccba", "aaccba", and "abacba".
Of all the ways, "aaccba" is the lexicographically smallest.

Example 2:

Input: palindrome = "a"
Output: ""
Explanation: There is no way to replace a single character to make "a" not a palindrome, so return an empty string.

 

Constraints:

• 1 <= palindrome.length <= 1000
• palindrome consists of only lowercase English letters.

---

문제 풀이

• 팰린드롬 문자열이 주어진다. 
• 펠린드롬은 문자열을 반으로 접었을때 데칼코마니처럼 똑같은 문자열을 말한다.
• 이 펠린드롬 문자열을 펠린드롬이 아니게 만들어야하는데 하나의 문자만 바꿀 수 있다.
• 문자 하나를 바꿨을때 사전순으로 가장 작은 문자열을 만들어야한다.
• 제한 사항을 보면 문자열의 최대길이는 1000이다. 
• 시간복잡도에서 걸릴만한 조건은 없는것 같으며, 
• 앞에서 부터 중간(이 이후 부터는 같은 문자이기 때문에)까지 확인하면서 a 가 아닌 문자가 있다면 a 로 치환해준다. 
• 앞에 있는 문자가 작을 수록 사전순으로 가장 작을 수 있기 때문이다.
• 만약 맨 앞부터 중간까지 모두 a 로 채워져 있다면, 가장 마지막 문자를 b 로 바꾼다.
• 즉, 모든 문자가 a 일 경우는 가장 마지막 문자를 a 다음 문자인 b 로 바꾸면 가장 작은 문자열이 된다. 

소스 코드

class Solution:
    def breakPalindrome(self, palindrome: str) -> str:
        if len(palindrome) == 1:
            return ''
        for i in range(len(palindrome) // 2):
            if palindrome[i] != 'a':
                tmp = list(palindrome)
                tmp[i] = 'a'
                return ''.join(tmp)
        tmp = list(palindrome)
        tmp[len(palindrome) - 1] = 'b'
        return ''.join(tmp)