[LeetCode] No 5. Longest Palindromic Substring

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

Longest Palindromic Substring - LeetCode

[Problem]

Given a string s, return the longest palindromic substring in s

 

[Explanation]

Honestly, I searched the meaing of palidromic. It is strings or sentences like 'abcba', which has the same pronounciation when reading from front or back. 

This problem's purpose is to find the longest palindromic.

 

[Solution]

1) First, I make a standard in the string like below

ex) anmvikivf

Using for states I make standard. 

when i = 0, standard is 'a'

when i = 1, stnadard is 'n'

...

when i = 8, standard is 'f'

 

2) Second, I split the candidates as two cased such as odd string, even string

In case of odd, it needs to check whether (i+1), (i-1) characteristics are the same.

In case of even, standard i is used, So it compares between i, (i+1) characteristics.

 

3) If two characteristics are the same, looked string has to be expanded.

Like, in case of odd, (i+2) and (i-2). 

In case of even, (i-1) and (i+2)

 

4) Also, when checking the same characteristics, it needs to count how long string's length is.

Therefore, I define 'ans' to save a number of longest string's length.

Additionally, I save 'start_idx' and 'end_idx' to save the location where the longest string is happend.

 

class Solution:     def longestPalindrome(self, s: str) -> str:         if len(s) == 1: return s         cnt = 0         ans = 1         start_idx = 0         end_idx = 0                  for i in range(len(s)):                             #odd             odd_i = 1             odd_cnt = 1             while(i-odd_i >= 0 and i+odd_i < len(s) and s[i-odd_i] == s[i+odd_i]):                 odd_cnt += 2                 odd_i += 1                          if ans < odd_cnt:                 ans = odd_cnt                 end_idx = i + odd_i - 1                 start_idx = i - odd_i + 1                                               #even             even_i = 0             even_cnt = 0             while(i-even_i >= 0 and i+(even_i+1) < len(s) and s[i-even_i] == s[i+even_i+1]):                 even_cnt += 2                 even_i += 1                          if ans < even_cnt:                 ans = even_cnt                 end_idx = i + even_i                 start_idx = i - even_i  + 1                          return s[start_idx:end_idx+1]