Programming Languages war Python, PHP, Javascript (Nodejs) Longest Palindromic Substring

English

Hey my friends, a new post about this war. I don't know which is better, but I'll try to figure it out. I hope y'all enjoy this series. Here we go!

This is a challenge of leetcode.com I made this challenge with Python3, and next I made PHP and Javascript the same way.

Problem:

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

Example 1:

Input: s = "babad" Output: "bab" Note: "aba" is also a valid answer.

Have to tell you all that I used a super power called google 😅 to figure out how to get if a piece of a string is a palindromic. Here the details en.wikipedia.org/wiki/Longest_palindromic_s..

First, I need an odd length to get the correct palindromic string to achieve that, the docs recommends to use any symbol.

Then I'm going to explain in each language, so, here we go!

Python

First, I need to add a symbol, I used the method "while" to add symbols between letters, I'm going to loop the string like a dictionary, then I had to validate if to right or to left exist the same letter or symbol if exist increase the "radius". If "radius" is greater than "palindrome" variable, I update the variable and set the "maxCenter" variable, In the end, I get the minimum and maximum from the string to get the palindromic string.

class Solution:
  def longestPalindrome(self, s: str):
    c = 0
    ss = '|'
    while (c < len(s)):
      ss = ss + s[c] + '|'
      c += 1

    palindrome = 0

    center = 0
    maxCenter = 0
    while (center < len(ss)):
      radius = 0

      while (
          center - (radius + 1) >= 0 and
          center + (radius + 1) < len(ss) and
          ss[center - (radius + 1)] == ss[center + (radius + 1)]
      ):
        radius = radius + 1

      if radius > palindrome:
        palindrome = radius
        maxCenter = center

      center = center + 1

    r = ''

    minimum = maxCenter - palindrome
    maximum = maxCenter + palindrome
    while (minimum <= maximum):
        if (ss[minimum] != '|'):
          r = r + ss[minimum]

        minimum += 1

    return r


sol = Solution()
result = sol.longestPalindrome('book')
print(result)

PHP

First, I need to add a symbol, but in PHP I can't use a string like an array, I have to turn the string to array with the method "str_split", I used the method "while" to add symbols between letters in an array, I'm going to loop the array, then I had to validate if to right or to left exist the same letter or symbol if exist increase the "radius". If "radius" is greater than "palindrome" variable, I update the variable and set the "maxCenter" variable, In the end, I get the minimum and maximum from the string to get the palindromic string.

<?php
class Solution
{
    public function longestPalindrome($s)
    {
        $c  = 0;
        $s  = str_split($s);
        $ss = ['|'];
        while ($c < count($s)) {
            $ss[] = $s[$c];
            $ss[] = '|';
            $c++;
        }
        $palindrome = 0;
        $center     = 0;
        $maxCenter  = 0;

        while ($center < count($ss)) {
            $radius = 0;

            while (
                $center - ($radius + 1) >= 0 &&
                $center + ($radius + 1) < count($ss) &&
                $ss[$center - ($radius + 1)] == $ss[$center + ($radius + 1)]
            ) {
                $radius = $radius + 1;
            }

            if ($radius > $palindrome) {
                $palindrome = $radius;
                $maxCenter  = $center;
            }

            $center = $center + 1;
        }
        $r   = '';
        $min = $maxCenter - $palindrome;
        $max = $maxCenter + $palindrome;
        while ($min <= $max) {
            if ($ss[$min] !== '|') {
                $r = $r . $ss[$min];
            }
            $min += 1;
        }

        return $r;
    }
}

$sol    = new Solution();
$result = $sol->longestPalindrome('book');
var_dump($result);
?>

Javascript

First, I need to add a symbol, I used the method "while" to add symbols between letters, I'm going to loop the string like an array, then I had to validate if to right or to left exist the same letter or symbol if exist increase the "radius". If "radius" is greater than "palindrome" variable, I update the variable and set the "maxCenter" variable, In the end, I get the minimum and maximum from the string to get the palindromic string.

class Solution {
  longestPalindrome(s) {
    let c = 0;
    let ss = '|';
    while (c < s.length) {
      ss = ss + s[c] + '|';
      c++;
    }

    let palindrome = 0;

    let center = 0;
    let maxCenter = 0;
    while (center < ss.length) {
      let radius = 0;

      while (
        center - (radius + 1) >= 0 &&
        center + (radius + 1) < ss.length &&
        ss[center - (radius + 1)] == ss[center + (radius + 1)]
      ) {
        radius = radius + 1;
      }

      if (radius > palindrome) {
        palindrome = radius;
        maxCenter = center;
      }

      center = center + 1;
    }
    let r = '';

    let min = maxCenter - palindrome;
    let max = maxCenter + palindrome;
    while (min <= max) {
      if (ss[min] !== '|') {
        r = r + ss[min];
      }
      min += 1;
    }
    return r;
  }
}

const sol = new Solution();
const result = sol.longestPalindrome('book');
console.log(result);

Conclusion

  • Structure: You can see that in Python I had to change the variable name of min to minimum and of max to maximum because in Python exists these words like methods, in PHP I had to change the string to array.
  • Lines: Python: 44, PHP: 53, Javascript: 48
  • Time to execution: Python: 4336 ms, PHP: 832 ms, Javascript: 144 ms
  • Memory Usage: Python: 14.3 MB, PHP: 15.9 MB, Javascript: 44.9 MB

Would you like that I write about more challenges?

I hope you enjoy my post and remember that I am just a Dev like you!

No Comments Yet