[HackerRank] Palindrome Index

Given a string of lowercase letters in the range ascii[a-z], determine the index of a character that can be removed to make the string a palindrome. There may be more than one solution, but any will do. If the word is already a palindrome or there is no solution, return -1. Otherwise, return the index of a character to remove.

 

Example

s = "bcbc"

Either remove 'b' at index 0 or 'c' at index 3.

 

Function Description

Complete the palindromeIndex function in the editor below.

palindromeIndex has the following parameter(s):

• string s: a string to analyze

Returns

• int: the index of the character to remove or -1

Input Format

The first line contains an integer q, the number of queries.
Each of the next q lines contains a query string s.

Constraints

• 1 ≤ q ≤ 20
• 1 ≤ length of s ≤ 10^5 + 5
• All characters are in the range ascii[a-z].

Sample Input

STDIN   Function
-----   --------
3       q = 3
aaab    s = 'aaab' (first query)
baa     s = 'baa'  (second query)
aaa     s = 'aaa'  (third query)

Sample Output

3
0
-1

Explanation

Query 1: "aaab"
Removing 'b' at index 3 results in a palindrome, so return 3.

Query 2: "baa"
Removing 'b' at index 0 results in a palindrome, so return 0.

Query 3: "aaa"
This string is already a palindrome, so return -1. Removing any one of the characters would result in a palindrome, but this test comes first.

 

Note: The custom checker logic for this challenge is available here.

---

소문자로 구성된 문자열이 주어졌을 때, 해당 문자열에서 한 문자를 제거해 회문(앞뒤가 같은 문자열)으로 만들 수 있는 인덱스를 찾으세요. 가능한 해답이 여러 개일 경우 아무 인덱스나 반환해도 됩니다. 만약 문자열이 이미 회문이거나 제거해도 회문을 만들 수 없다면 -1을 반환하세요.

 

예제

• s = "bcbc"
• 0번 인덱스의 'b'를 제거하거나 3번 인덱스의 'c'를 제거하여 회문을 만들 수 있습니다.

함수 설명

함수 시그니처

public static int palindromeIndex(String s)

 

매개변수

• string s: 분석할 문자열

반환값

• int: 회문을 만들기 위해 제거할 문자의 인덱스, 또는 불가능한 경우 -1

입력 형식

• 첫 번째 줄에는 쿼리 개수 q가 주어집니다.
• 각 쿼리 s는 소문자로만 구성된 문자열입니다.

제약 사항

• 1 ≤ q ≤ 20
• 1 ≤ length of s ≤ 10^5 + 5
• 모든 문자는 [a-z] 범위의 ASCII 문자를 사용합니다.

 

입력 예제

3 
aaab 
baa 
aaa

 

출력 예제

3 
0 
-1

 

설명

• 첫 번째 쿼리 "aaab": 인덱스 3의 'b'를 제거하면 회문이 됩니다.
• 두 번째 쿼리 "baa": 인덱스 0의 'b'를 제거하면 회문이 됩니다.
• 세 번째 쿼리 "aaa": 이미 회문이므로 -1을 반환합니다.

 

728x90

 

Solution

---

public static int palindromeIndex(String s) {
    int left = 0;
    int right = s.length() - 1;

    while (left < right) {
        if (s.charAt(left) != s.charAt(right)) {
            // Check if removing the left character results in a palindrome
            if (isPalindrome(s, left + 1, right)) {
                return left;
            }
            // Check if removing the right character results in a palindrome
            else if (isPalindrome(s, left, right - 1)) {
                return right;
            }
            // If neither removal results in a palindrome, return -1
            else {
                return -1;
            }
        }
        left++;
        right--;
    }

    // The string is already a palindrome
    return -1;
}

// Helper function to check if a substring is a palindrome
private static boolean isPalindrome(String s, int left, int right) {
    while (left < right) {
        if (s.charAt(left) != s.charAt(right)) {
            return false;
        }
        left++;
        right--;
    }
    return true;
}

 

• palindromeIndex 함수:
  • 두 포인터 left와 right를 이용해 문자열의 양 끝에서 시작해 서로를 향해 이동하며 비교합니다.
  • 만약 s.charAt(left)와 s.charAt(right)가 같지 않다면, isPalindrome 함수로 두 경우를 확인합니다.
    • left + 1에서 시작해 right까지가 회문인 경우: 인덱스 left를 반환.
    • left에서 시작해 right - 1까지가 회문인 경우: 인덱스 right를 반환.
    • 둘 중 어느 경우도 회문이 아니면 -1을 반환합니다.
  • 두 포인터가 교차할 때까지 문제 없이 확인이 완료되면 문자열은 이미 회문이므로 -1을 반환합니다.
• isPalindrome 함수:
  • 주어진 인덱스 범위 내의 문자열이 회문인지 확인하는 보조 함수입니다.