Return to Answer

added 32 characters in body

Source Link

edited Oct 12, 2022 at 9:52

A possible implementation is given below as a reference. As mentioned in the other answer, slicing a string creates a copy, which is quite an expensive operation. One way to further improve this algorithm, is to workThis implementation works with indices and pass a reference to s around, instead of creating slices ofstring slicing s all(see the timeother answer) to further speedup the algorithm.

class Solution:
    def countCommonStartingCharscount_palindromic_chars(self, s1s: str, s2idx: strint, even_length: bool) -> int:
        """ Returns the number of commonpalindromic characters in s at theposition startidx of"""


 s1 and s2 """
    len_s = len(s)
        chars_countershift = 0 

        # Keep going until the string's end and characters are still palindrome
        while (chars_counteridx <- min(len(s1),shift len(s2))>= 0 and idx + shift + even_length < len_s and
                s1[chars_counter]s[idx - shift] == s2[chars_counter]s[idx + shift + even_length]):
            chars_countershift += 1

        return chars_countershift

    def longestPalindromelongest_palindrome(self, s: str) -> str:
        """ Returns the first longest palindrome substring of s """

        longest = ''
        for n in range(0, len(s)):
            # split after nth char / palindromes of even length
            length = self.countCommonStartingCharscount_palindromic_chars(s[n::-1]s, s[n+1:]n, True)

            if 2 * length > len(longest):
                longest = s[n-length+1:n+length+1]

            # split at nth char / palindromes of odd length
            length = self.countCommonStartingCharscount_palindromic_chars(s[n::-1]s, s[n:]n, False)

            if 2 * length - 1 > len(longest):
                longest = s[n-length+1:n+length]

        return longest


testsuite = {
    # palindromes with odd length
    'abcdcth': 'cdc',
    'abacdfg': 'aba',
    'abcdefe': 'efe',

    # palindromes with even length
    'abbacdefg': 'abba',
    'abcdeffedcklm': 'cdeffedc',

    # even length; entire string is palindrome
    'abcddcba': 'abcddcba',

    # all the same characters
    'a': 'a',
    'aa': 'aa',
    'aaa': 'aaa',
    'aaaa': 'aaaa',

    # start with different character than all the same characters
    'ba': 'b',  # first palindrome is 'b', not 'a'
    'baa': 'aa',
    'baaa': 'aaa',
    'baaaa': 'aaaa',

    # all the same characters and end with different character
    'aab': 'aa',
    'aaab': 'aaa',

    # palindrome of length 1
    'abcdef': 'a',

    # two palindromes in one string (last one longer)
    'abcbdefghhgfekl': 'efghhgfe',
    'abcbdefedh': 'defed'
}

s = Solution()
for case, result in testsuite.items():
    observed = s.longestPalindromelongest_palindrome(case)
    print(f"{case} -> {observed}; "
          f"this is{' NOT' if observed != result else ''} correct")

Try it online!Try it online!

A possible implementation is given below as a reference. As mentioned in the other answer, slicing a string creates a copy, which is quite an expensive operation. One way to further improve this algorithm, is to work with indices and pass a reference to s around, instead of creating slices of s all the time.

class Solution:
    def countCommonStartingChars(self, s1: str, s2: str) -> int:
        """ Returns the number of common characters at the start of s1 and s2 """

        chars_counter = 0

        while (chars_counter < min(len(s1), len(s2)) and
                s1[chars_counter] == s2[chars_counter]):
            chars_counter += 1

        return chars_counter

    def longestPalindrome(self, s: str) -> str:
        """ Returns the first longest palindrome substring of s """

        longest = ''
        for n in range(0, len(s)):
            # split after nth char / palindromes of even length
            length = self.countCommonStartingChars(s[n::-1], s[n+1:])

            if 2 * length > len(longest):
                longest = s[n-length+1:n+length+1]

            # split at nth char / palindromes of odd length
            length = self.countCommonStartingChars(s[n::-1], s[n:])

            if 2 * length - 1 > len(longest):
                longest = s[n-length+1:n+length]

        return longest


testsuite = {
    # palindromes with odd length
    'abcdcth': 'cdc',
    'abacdfg': 'aba',
    'abcdefe': 'efe',

    # palindromes with even length
    'abbacdefg': 'abba',
    'abcdeffedcklm': 'cdeffedc',

    # even length; entire string is palindrome
    'abcddcba': 'abcddcba',

    # all the same characters
    'a': 'a',
    'aa': 'aa',
    'aaa': 'aaa',
    'aaaa': 'aaaa',

    # start with different character than all the same characters
    'ba': 'b',  # first palindrome is 'b', not 'a'
    'baa': 'aa',
    'baaa': 'aaa',
    'baaaa': 'aaaa',

    # all the same characters and end with different character
    'aab': 'aa',
    'aaab': 'aaa',

    # palindrome of length 1
    'abcdef': 'a',

    # two palindromes in one string (last one longer)
    'abcbdefghhgfekl': 'efghhgfe',
    'abcbdefedh': 'defed'
}

s = Solution()
for case, result in testsuite.items():
    observed = s.longestPalindrome(case)
    print(f"{case} -> {observed}; "
          f"this is{' NOT' if observed != result else ''} correct")

Try it online!

A possible implementation is given below as a reference. This implementation works with indices instead of string slicing (see the other answer) to further speedup the algorithm.

class Solution:
    def count_palindromic_chars(self, s: str, idx: int, even_length: bool) -> int:
        """ Returns the number of palindromic characters in s at position idx """


        len_s = len(s)
        shift = 0 

        # Keep going until the string's end and characters are still palindrome
        while (idx - shift >= 0 and idx + shift + even_length < len_s and
                s[idx - shift] == s[idx + shift + even_length]):
            shift += 1

        return shift

    def longest_palindrome(self, s: str) -> str:
        """ Returns the first longest palindrome substring of s """

        longest = ''
        for n in range(0, len(s)):
            # split after nth char / palindromes of even length
            length = self.count_palindromic_chars(s, n, True)

            if 2 * length > len(longest):
                longest = s[n-length+1:n+length+1]

            # split at nth char / palindromes of odd length
            length = self.count_palindromic_chars(s, n, False)

            if 2 * length - 1 > len(longest):
                longest = s[n-length+1:n+length]

        return longest


testsuite = {
    # palindromes with odd length
    'abcdcth': 'cdc',
    'abacdfg': 'aba',
    'abcdefe': 'efe',

    # palindromes with even length
    'abbacdefg': 'abba',
    'abcdeffedcklm': 'cdeffedc',

    # even length; entire string is palindrome
    'abcddcba': 'abcddcba',

    # all the same characters
    'a': 'a',
    'aa': 'aa',
    'aaa': 'aaa',
    'aaaa': 'aaaa',

    # start with different character than all the same characters
    'ba': 'b',  # first palindrome is 'b', not 'a'
    'baa': 'aa',
    'baaa': 'aaa',
    'baaaa': 'aaaa',

    # all the same characters and end with different character
    'aab': 'aa',
    'aaab': 'aaa',

    # palindrome of length 1
    'abcdef': 'a',

    # two palindromes in one string (last one longer)
    'abcbdefghhgfekl': 'efghhgfe',
    'abcbdefedh': 'defed'
}

s = Solution()
for case, result in testsuite.items():
    observed = s.longest_palindrome(case)
    print(f"{case} -> {observed}; "
          f"this is{' NOT' if observed != result else ''} correct")

Try it online!

Source Link

answered Oct 12, 2022 at 8:39

agtoever

Variable naming

I'd like to recommend the book Clean code by Robert C. Martin (Amazon link), which gives very concrete hints about variable naming. Most of your variable names don't describe what that variable means. For example:

dp describes the algorithm, not what the values in the matrix mean; maybe longest_palindrome is a bit long, but describes it better,
row and col are clearly indices, but don't describe what the rows and columns mean; starting_pos and palindrome_length describes better what is does (assuming this is the correct meaning of row and col; I'm not sure of that,
n is used for the string length; so name it accordingly: len_s

Now dp[row][col] doesn't tell me anything. While longest_palindrome[starting_pos][palindrome_length] is a more meaningful name. Again: not sure about the row/col meaning, but I'm sure you get the point.

Speeding it up

Your core question is about performance. Right now you have an algorithm that takes a squared amount of time (and memory) when scaling up: O(n^2). This means that if you double the string length, you need 2*2 = 4 times the time and memory. In general O(n^2) is quite bad: takes a long time, takes a lot of memory, so you should look at improving that.

In most of these challenges, you can (or must) exploit the properties of the information in the question to create a solution. In this case, you know that a palindrome consists of a mirrored part of the same characters. A palindrome of even length has the same central characters, a palindrome of odd length has one central character. So one approach is to loop over s, and see what is the length of the palindrome at the current character. This algorithm has O(n * log(n)). The log(n) comes from checking the length of the palindrome from a given character.

In summary: another algorithm is needed to speed-up your solution.

A possible implementation is given below as a reference. As mentioned in the other answer, slicing a string creates a copy, which is quite an expensive operation. One way to further improve this algorithm, is to work with indices and pass a reference to s around, instead of creating slices of s all the time.

class Solution:
    def countCommonStartingChars(self, s1: str, s2: str) -> int:
        """ Returns the number of common characters at the start of s1 and s2 """

        chars_counter = 0

        while (chars_counter < min(len(s1), len(s2)) and
                s1[chars_counter] == s2[chars_counter]):
            chars_counter += 1

        return chars_counter

    def longestPalindrome(self, s: str) -> str:
        """ Returns the first longest palindrome substring of s """

        longest = ''
        for n in range(0, len(s)):
            # split after nth char / palindromes of even length
            length = self.countCommonStartingChars(s[n::-1], s[n+1:])

            if 2 * length > len(longest):
                longest = s[n-length+1:n+length+1]

            # split at nth char / palindromes of odd length
            length = self.countCommonStartingChars(s[n::-1], s[n:])

            if 2 * length - 1 > len(longest):
                longest = s[n-length+1:n+length]

        return longest


testsuite = {
    # palindromes with odd length
    'abcdcth': 'cdc',
    'abacdfg': 'aba',
    'abcdefe': 'efe',

    # palindromes with even length
    'abbacdefg': 'abba',
    'abcdeffedcklm': 'cdeffedc',

    # even length; entire string is palindrome
    'abcddcba': 'abcddcba',

    # all the same characters
    'a': 'a',
    'aa': 'aa',
    'aaa': 'aaa',
    'aaaa': 'aaaa',

    # start with different character than all the same characters
    'ba': 'b',  # first palindrome is 'b', not 'a'
    'baa': 'aa',
    'baaa': 'aaa',
    'baaaa': 'aaaa',

    # all the same characters and end with different character
    'aab': 'aa',
    'aaab': 'aaa',

    # palindrome of length 1
    'abcdef': 'a',

    # two palindromes in one string (last one longer)
    'abcbdefghhgfekl': 'efghhgfe',
    'abcbdefedh': 'defed'
}

s = Solution()
for case, result in testsuite.items():
    observed = s.longestPalindrome(case)
    print(f"{case} -> {observed}; "
          f"this is{' NOT' if observed != result else ''} correct")

Try it online!