Palindromic Characteristics

Palindromic characteristics of string A with length ** A ** is a sequence of ** A ** integers, where kth number is the total number of non-empty substrings of A which are k-palindromes.

A string is 1-palindrome if and only if it reads the same backward as forward.

A string is k-palindrome (k > 1) if and only if:

  • Its left half equals to its right half.

  • Its left and right halfs are non-empty (k - 1)-palindromes.

The left half of string t is its prefix of length ** t //2**, and right half — the suffix of the same length. ** t //2** denotes the length of string t divided by 2, rounded down.

Note that each substring is counted as many times as it appears in the string. For example, in the string “aaa” the substring “a” appears 3 times.

Input Format:

    First and only argument of input contains a string A

Output Format:

    Return a |A| length integer array denoting palindromic characteristic of string A

Constraints:

    1 <= |A| <= 3000

For Example:

Example Input 1:
    A = "abba"
Example Output 1:
    [6, 1, 0, 0]
Explanation 1:
    1-palindromes are substring «a», «b», «b», «a», «bb», «abba», the substring «bb» is 2-palindrome. There are no 3- and 4-palindromes here.
Example Input 2:
    A = "abacaba"
Example Output 2:
    [12, 4, 1, 0, 0, 0, 0]
NOTE: You only need to implement the given function. Do not read input, instead use the arguments to the function. Do not print the output, instead return values as specified. Still have a doubt? Checkout Sample Codes for more details.
Start solving Palindromic Characteristics on Interview Code Editor
Sign Up
to access hints and editorial solutions for Palindromic Characteristics

Discussion


Loading...
Click here to start solving coding interview questions