Longest palindromic substring

input

string = "abaxyzzyxf"

output

"xyzzyx"

---

Approach #1

/*
I: string
O: string
C: 적어도 하나의 longest palindromic substring이 존재함
E:

palindromic= forward랑 backward가 같은것
첫문자, 끝문자가 같고 그 안의 문자가 palindromic이어야함

모든 substring 돌면서 그게 palindromic인지 확인...?

string="abaxyzzyxf"
        ^
        ^
        
"xyzzyx"

xyzzyx
i
     j
     
j-1+1/2 만큼 for문 돌면서
string[i+a] string[j-a] 같은지 비교하기.
다르면 false.
다같으면 true.

     
ababa

*/

Solution #1

//const string="abaxyzzyxf";
const string="acacacb";
//ab 0,1
// 0 1
function longestPalindromicSubstring(string){
  let maxStr="";
  let isPalindromic = false;
  // edge case
  if(!string) return;
  if(string.length===1 && string.length===2) return string;

  for(let i=0; i<string.length;i++){
    for(let j=i; j<string.length; j++){
      isPalindromic=true;
      // palindromic 여부 확인
      for(let p=0; p<(j-i+1)/2; p++){
        if(string[i+p]!==string[j-p]) isPalindromic=false;
      }
      // longest palindromic 여부 확인
      if(isPalindromic && (j-i+1 > maxStr.length)){
        maxStr=string.substr(i,j-i+1);
      }
    }
  }
  return maxStr;
}

console.log(longestPalindromicSubstring(string));

Time Complexity

O(N^3)

N: string.length
모든 substring을 확인하기위해 N*N만큼의 시간복잡도가 필요한데, 그 substring이 palindromic substring인지 확인하기 위해 또 반복문을 돌게 된다. 따라서 시간복잡도는 N^3.
=> leetcode 같은데서 이렇게 코드 짜면 무조건 Time Limit 뜬다... vscode에서 돌아가긴 하지만 코드 개선 필요...

Space Complexity

space: O(N)

N: string.length
전체 string이 palindromic substring인 경우가 가장긴 maxStr이 될것이므로 공간복잡도는 N.

---

Approach #2

palindromic substring이 되려면 
1) 첫 문자랑 끝 문자가 같아야함
-> 반복문에서 substring 가져올때 나랑 끝 문자가 같은 애들만 가져온다면?
"abaxyzzyxf" 
-> aba, xyzzzyx, yzzy, zz 이렇게.
-> 그 문자에서 첫문자, 끝문자를 지우고 그 지워진 문자의 처음과 끝이 같은지 비교한다면?

로직 생각해보기만 하고 코드 안짜봄,,, 나중에 짜보자^.^
=> 근데 이래도 시간복잡도 똑같은데.... ㅠㅠㅠㅠ