LeetCode - Break a Palindrome

문제 설명

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.

제약사항

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

Solution

[전략]
1. 앞자리에서부터 더 작은 알파벳으로 변경할수 있는지 확인

• 홀수인 경우 중간 자리는 바뀌어봤자 palindrome이기 때문에 제외
• a가 아니면 a가 무조건 제일 작은 알파벳이므로 a로 변경
• a이면 더 작은 알파벳으로 변경할수 없으므로 다음 index 알파벳 체크

2. String이 모두 a로 구성된 경우에는 return 되지 못하고 for문을 빠져나오므로 제일 마지막 자리를 'b'로 변경해줌.

class Solution {

    public String breakPalindrome(String palindrome) {

        char[] strArr = palindrome.toCharArray();
        int strLen = strArr.length;
        if (strLen < 2) {
            return "";
        }

        for (int i = 0; i < strLen; i++) {
            if ((strLen & 1) == 1 && i == strLen / 2) { // 홀수
                continue;
            }
            if (strArr[i] != 'a') {
                strArr[i] = 'a';
                return String.valueOf(strArr);
            }
        }

        strArr[strLen - 1] = 'b';
        return String.valueOf(strArr);
    }
}