<Medium> Longest Palindromic Substring (LeetCode : C#)

https://leetcode.com/problems/longest-palindromic-substring/

📕 문제 설명

문자열 s가 주어질 때 가장 긴 palindrome 부분 문자열 반환

• palindrome: 거꾸로 해도 같은 문자열 (ex - 토마토, 역삼역 등..)

• Input
  문자열 s
• Output
  가장 긴 palindrome 부분 문자열

예시

같은 문제 푼적이 많은 것 같은데 볼때마다 새롭게 푸는 느낌이다😂. 계속 개수를 기준으로 substring후 해당 문자가 palindrome인지 확인하는 방식으로 접근했는데 time limit뜨면서 잘 안되었다. (이 방식은 결국 개수 for문 1개, 첫 index 잡는 for문 1개, palindrome 확인하는 for문 1개라서 너무 비효율적이긴 하다.) 기준 문자 기준으로 확인한다는 것만 생각하면 쉽게 풀리는 문제다!

풀이

1. 기준이될 문자 선택 (for - i 문)

2. 홀수 개수일 경우 기준 문자 기준 -j, +j에 해당되는 문자가 같은지 비교하며 count 세기
   2-1) 같으면 계속 진행
   2-2) 다르면 break
   2-3) count를 기준으로 substring {ex - cabad일때 b가 기준 문자면 count가 최종적으로 1이됨, b기준 count만큼 뺀 index에서 count * 2 + 1의 길이만큼 substring)

3. 짝수 개수일 경우 기준 문자가 2개이다. 여기서 기준 문자가 같은지 확인하고 같다면 palindrome check를 진행한다. 방식은 홀수일때와 같다.
   3-1) 기준 문자 중 왼쪽을 기준으로 -j, 오른쪽을 기준으로 +j에 해당되는 문자가 같은지 비교하며 count 세기
   3-2) 같으면 계속 진행, 다르면 break 후 substring

4. 정답보다 더 긴 것이 있다면 그것으로 변경

public class Solution {
    public string LongestPalindrome(string s) {

        if (s.Length == 1 || (s.Length == 2 && s[0] == s[1])) return s;

        string answer = s[0].ToString();
        string oddS = "";
        string evenS = "";

        for (int i = 1; i < s.Length; i++)
        {
            oddS = FindOddPalindrome(i, s);
            if (s[i-1] == s[i]) // 같은 경우만 확인
            {
                evenS = FindEvenPalindrome(i - 1, i, s);
            }
			// 길이 비교해서 answer 갱신
            if (answer.Length < oddS.Length) answer = oddS;
            if (answer.Length < evenS.Length) answer = evenS;
        }

        return answer;
        
    }
	// 홀수 개수의 palindrome
    public string FindOddPalindrome(int middleI, string s)
    {
        int count = 0;
        for (int j = 1; j < s.Length; j++)
        {
            if (middleI - j < 0 || middleI + j >= s.Length) break;
            if (s[middleI - j] == s[middleI + j]) count += 1;
            else break;
        }

        return s.Substring(middleI - count, count * 2 + 1);
    }
	// 짝수 개수의 palindrome 
    public string FindEvenPalindrome(int middleI1, int middleI2, string s)
    {
        int count = 0;
        for (int j = 1; j < s.Length; j++)
        {
            if (middleI1 - j < 0 | middleI2 + j >= s.Length) break;
            if (s[middleI1 - j] == s[middleI2 + j]) count += 1;
            else break;
        }
 
        return s.Substring(middleI1 - count, count * 2 + 2);
    }
}

결과