[LeetCode/Easy] 2697. Lexicographically Smallest Palindrome

1. Input

1) String s

 

2. Output

1) s의 문자를 1번에 1개씩 바꾸는 작업을 했을 때, 최소한의 작업 횟수로 만들 수 있는 팰린드롬 중 사전순으로 가장 앞에 오는 문자열을 반환

- 팰린드롬(palindrome)은 앞에서부터 읽으나 뒤에서부터 읽으나 같은 문자열을 말한다.

 

3. Constraint

1) 1 <= s.length <= 1000

2) s는 영어 소문자로 이루어져 있다.

 

4. Example

Input: s = "egcfe" -> Output: "efcfe"

Input: s = "abcd" -> Output: "abba"

 

5. Code

1) 첫 코드

class Solution {
    public String makeSmallestPalindrome(String s) {
        char[] arr = s.toCharArray();
        for(int i=0 ; i<=arr.length/2 ; i++){
            char c = arr[i]<arr[arr.length-1-i] ? arr[i] : arr[arr.length-1-i];
            arr[i] = c;
            arr[arr.length-1-i] = c;
        }
        return new String(arr);
    }
}

- 89%, 61%

 

2) two pointers를 보고 다시 해본 코드

class Solution {
    public String makeSmallestPalindrome(String s) {
        char[] arr = s.toCharArray();
        int i = 0, j = arr.length-1;
        while(i<j){
            if(arr[i]<arr[j]) arr[j] = arr[i];
            else arr[i] = arr[j];
            i++; j--;
        }
        return new String(arr);
    }
}

- 89%, 96%

- 코드도 훨씬 간결해졌고, 메모리 사용량도 줄었다.

- 역시 힌트