2193. Minimum Number of Moves to Make Palindrome / TypeScipt

You are given a string s consisting only of lowercase English letters.

In one move, you can select any two adjacent characters of s and swap them.

Return the minimum number of moves needed to make s a palindrome.

Note that the input will be generated such that s can always be converted to a palindrome.

 

Example 1:

Input: s = "aabb"
Output: 2
Explanation:
We can obtain two palindromes from s, "abba" and "baab". 
- We can obtain "abba" from s in 2 moves: "aabb" -> "abab" -> "abba".
- We can obtain "baab" from s in 2 moves: "aabb" -> "abab" -> "baab".
Thus, the minimum number of moves needed to make s a palindrome is 2.

Example 2:

Input: s = "letelt"
Output: 2
Explanation:
One of the palindromes we can obtain from s in 2 moves is "lettel".
One of the ways we can obtain it is "letelt" -> "letetl" -> "lettel".
Other palindromes such as "tleelt" can also be obtained in 2 moves.
It can be shown that it is not possible to obtain a palindrome in less than 2 moves.

 

출처 : https://leetcode.com/problems/minimum-number-of-moves-to-make-palindrome/description/

 

 

풀이 

function minMovesToMakePalindrome(s: string) {
    let res = 0;
    let a = s.split("");

    while(a.length > 1) { 
        let i = a.indexOf(a[a.length - 1]);

        if(i === a.length - 1) {
            res += Math.floor(i/2);
        } else {
            res += i;
            // Splicing to remove the found character
            a.splice(i, 1);
        }
        // Popping to remove the end character
        a.pop();
    }

    return res;
};

 

문자열을 팰린드롬으로 만들기 위해 필요한 최소 이동 횟수를 계산하는 함수

팰린드롬은 앞에서 읽으나 뒤에서 읽으나 동일한 문자열을 의미

 

코드 설명

1. 변수 초기화:
   • res는 이동 횟수를 저장하는 변수
   • a는 입력 문자열 s를 문자 배열로 변환한 것
2. 반복문:
   • while(a.length > 1) 루프를 통해 배열 a의 길이가 1보다 큰 동안 반복
   • 배열의 길이가 1이면 더 이상 비교할 필요가 없으므로 종료
3. 문자 찾기:
   • let i = a.indexOf(a[a.length - 1])는 현재 배열의 마지막 문자와 같은 문자의 인덱스를 찾음
4. 인덱스 확인:
   • if(i === a.length - 1) 조건을 통해 찾은 문자가 배열의 마지막 문자와 같은지 확인
   • 같다면, 해당 문자가 이미 맞는 위치에 있으므로 이동 횟수는 Math.floor(i/2)로 계산.
   • 이는 중간에 있는 문자가 서로 맞춰지는 경우를 고려한 것
5. 문자 제거:
   • 만약 찾은 문자가 배열의 마지막 문자와 다르다면, res에 i를 더하고, a.splice(i, 1)을 통해 찾은 문자를 배열에서 제거.
   • 이후 a.pop()으로 마지막 문자를 제거
6. 결과 반환:
   • 최종적으로 이동 횟수를 담고 있는 res를 반환

 

 

예시 s = "letelt"

초기 설정

1. 입력 문자열 s = "letelt"
2. res를 0으로 초기화
3. 문자열을 문자 배열로 나눔: a = ['l', 'e', 't', 'e', 'l', 't'].

첫 번째 반복

• 배열 상태: ['l', 'e', 't', 'e', 'l', 't']
• 마지막 문자인 't'를 확인. 배열에서 첫 번째 위치를 찾음
  • i = a.indexOf('t') → i = 2 (첫 번째 't'의 인덱스).
• i가 a.length - 1 (5)와 같지 않으므로, res에 i를 더함
  • res += i → res = 0 + 2 = 2.
• 찾은 문자를 제거
  • a.splice(2, 1) → a는 ['l', 'e', 'e', 'l', 't'].
• 마지막 문자를 제거
  • a.pop() → a는 ['l', 'e', 'e', 'l'].

두 번째 반복

• 배열 상태: ['l', 'e', 'e', 'l']
• 마지막 문자인 'l'을 확인
  • i = a.indexOf('l') → i = 0.
• i가 a.length - 1과 같지 않으므로 res에 i를 더함
  • res += i → res = 2 + 0 = 2.
• 찾은 문자를 제거
  • a.splice(0, 1) → a는 ['e', 'e', 'l']
• 마지막 문자를 제거
  • a.pop() → a는 ['e', 'e']

세 번째 반복

• 배열 상태: ['e', 'e']
• 마지막 문자인 'e'을 확인
  • i = a.indexOf('e') → i = 0.
• i가 a.length - 1과 같지 않으므로 res에 i를 더함
  • res += i → res = 2 + 0 = 2.
• 찾은 문자를 제거
  • a.splice(0, 1) → a는 ['e'] 
• 마지막 문자를 제거
  • a.pop() → a는 [].

종료

• 이제 배열 a가 비었으므로 반복이 종료.
• 최종 결과인 res는 2