HackerRank Palindromic Border Problem Solution

Yashwant Parihar,

In this post, we will solve HackerRank Palindromic Border Problem Solution.

A border of a string is a proper prefix of it that is also a suffix. For example:

a and abra are borders of abracadabra,
⚫ kan and kankan are borders of kankankan.
⚫de is a border of decode.
Note that decode is not a border of decode because it’s not proper.
A palindromic border is a border that is palindromic. For example,
⚫a and ana are palindromic borders of anabanana,
⚫l, lol and lolol are palindromic borders of lololol.
Let’s define P (s) as the number of palindromic borders of string s. For example, if 8 = lololol, then P(s) = 3.
Now, a string of length N has exactly N(N+1)/2 non-empty substrings (we count
substrings as distinct if they are of different lengths or are in different positions, even if they are the same string). Given a string s, consisting only of the first 8 lowercase letters of the English alphabet, your task is to find the sum of P (s’) for all the non-empty substrings s’ of s. In other words, you need to find:

where si…; is the substring of s starting at position & and ending at position j.
Since the answer can be very large, output the answer modulo 10 power 9 +7.
Input Format
The first line contains a string consisting of N characters.
Output Format
Print a single integer: the remainder of the division of the resulting number by 10 power 9 +7.

Sample Input 1

ababa

Sample Output 1

5

Sample Input 2

aaaa

Sample Output 2

10

Sample Input 3

abcacb

Sample Output 3

3

Explanation
S = ababa has 15 substrings but only 4 substrings have palindromic borders.
S1…3 aba P (S1…3)=1
S1…5 ababa P (S1…5) = 2
S2…4 bab P (S2…4) = 1
S3…5 aba P(S3…5)=1

HackerRank Palindromic Border Problem Solution
HackerRank Palindromic Border Problem Solution

Palindromic Border C Solution

#include<stdio.h>
#include<stdlib.h>
typedef long long ll;
int ri()
{
    int x;
    scanf("%d", &x);
    return x;
}
#define N 100000
char a[N+1];
struct Node
{ 
    int suff, l, c[26], cnt;
}b[N+2];
int getSuff(int i, int x)
{
    while( i - 1 - b[x].l < 0 || a[i-1-b[x].l] != a[i] )
        x = b[x].suff;
    return x;
}
int main()
{
    b[0].suff = 1;
    b[0].l = 0;
    b[1].suff = 1;
    b[1].l = -1;
    scanf("%s", a);
    int x = 1, y = 2, i;
    for( i = 0 ; a[i] ; i++ )
    {
        x = getSuff(i, x);
        if(!b[x].c[a[i]-'a'])
        {
            b[y].l = b[x].l + 2;
            b[y].suff = b[getSuff(i, b[x].suff)].c[a[i]-'a'];
            b[y].cnt = 0;
            b[x].c[a[i]-'a'] = y++;
        }
        x = b[x].c[a[i]-'a'];
        b[x].cnt++;
    }
    for( i = y ; --i >= 0 ; )
        b[b[i].suff].cnt += b[i].cnt;
    ll ans = 0;
    for( i = 2 ; i < y ; i++ )
    {
        int c = b[i].cnt;
        ans += (ll)( c - 1 ) * c / 2;
    }
    printf("%lld\n", ans%1000000007);
    return 0;
}

Palindromic Border C++ Solution

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000007
#define L 5000011
int sa[L];
int sai[L];
int lcp[L];
int v[L];
char s[L];
ll ts[L];
int p[L<<1];
char t[L<<1];
int m, n;
set<ll> found;
bool scomp(int i, int j) {
    return s[i] < s[j];
}
bool tscomp(int i, int j) {
    return ts[i] < ts[j];
}
void get_suffix_array() {
    for (int i = 0; i < n; i++) v[i] = i;
    sort(v, v + n, scomp);
    sai[v[0]] = 1;
    for (int i = 1; i < n; i++) {
        if (s[v[i]] == s[v[i - 1]]) {
            sai[v[i]] = sai[v[i - 1]];
        } else {
            sai[v[i]] = i+1;
        }
    }
    for (int p = 1; p <= n; p <<= 1) {
        for (int i = 0; i < n-p; i++) ts[i] = sai[i] * (n+1LL) + sai[i+p];
        for (int i = n-p; i < n; i++) ts[i] = sai[i] * (n+1LL);
        sort(v, v + n, tscomp);
        sai[v[0]] = 1;
        for (int i = 1; i < n; i++) {
            if (ts[v[i]] == ts[v[i - 1]]) {
                sai[v[i]] = sai[v[i - 1]];
            } else {
                sai[v[i]] = i+1;
            }
        }
    }
    for (int i = 0; i < n; i++) sai[i]--;
    for (int i = 0; i < n; i++) sa[sai[i]] = i;
}
void get_lcp() {
    for (int i = 0; i < n; i++) lcp[i] = 0;
    int l = 0;
    for (int i = 0; i < n-1; i++) {
        int k = sai[i];
        int j = k ? sa[k-1] : sa[n-1];
        while (j + l < n and s[i + l] == s[j + l]) {
            l++;
        }
        lcp[k] = l;
        if (l > 0) {
            l--;
        }
    }
}
void manacher() {
    // from wikipedia
    // t has been processed
    int center = 0, end = 0, left = 0, right = 0;
    for (int i = 1; i < m; i++) {
        if (i > end) {
            p[i] = 0;
            left = i - 1;
            right = i + 1;
        } else {
            int j = 2*center - i; // index on the other side
            if (p[j] < end - i) { // whole palindrome is inside
                p[i] = p[j];
                left = -1; // so we don't enter the loop below
            } else { 
                p[i] = end - i;
                right = end + 1;
                left = 2*i - right;
            }
        }
        while (left >= 0 and right < m and t[left] == t[right]) {
            p[i]++;
            left--;
            right++;
        }
        if (i + p[i] > end) {
            center = i;
            end = i + p[i];
        }
    }
}
struct Node {
    int i, j, v;
    Node *p, *l, *r;
    Node(int i, int j, Node *p = NULL): i(i), j(j), p(p) {
        if (j - i == 1) {
            l = r = NULL;
            v = lcp[i];
        } else {
            int k = i + j >> 1;
            l = new Node(i, k, this);
            r = new Node(k, j, this);
            v = min(l->v, r->v);
        }
    }
};
int node_minocc(Node *node, int v, int i) {
    // find maximum j, 0 <= j <= i such that a[j] < v
    while (node->l) {
        if (i < node->l->j) {
            node = node->l;
        } else {
            node = node->r;
        }
    }
    // now node->i = i < node->j = i+1
    if (node->v < v) {
        return node->i;
    }
    while (true) {
        while (node->p and node->p->l == node) {
            node = node->p;
        }
        if (!node->p) {
            return 0;
        }
        node = node->p;
        if (node->l->v < v) {
            node = node->l;
            break;
        }
    }
    while (node->l) {
        if (node->r->v < v) {
            node = node->r;
        } else {
            node = node->l;
        }
    }
    return node->i;
}
int node_maxocc(Node *node, int v, int i) {
    // find maximum j, i <= j <= n such that a[j] >= v
    if (i == n) {
        return n;
    }
    while (node->l) {
        if (i < node->l->j) {
            node = node->l;
        } else {
            node = node->r;
        }
    }
    // now node->i = i < node->j = i+1
    if (node->v < v) {
        return node->i;
    }
    while (true) {
        while (node->p and node->p->r == node) {
            node = node->p;
        }
        if (!node->p) {
            return n;
        }
        node = node->p;
        if (node->r->v < v) {
            node = node->r;
            break;
        }
    }
    while (node->l) {
        if (node->l->v < v) {
            node = node->l;
        } else {
            node = node->r;
        }
    }
    return node->i;
}
int main() {
    scanf("%s", s);
    n = strlen(s);
    // suffix tree
    get_suffix_array();
    get_lcp();
    Node *root = new Node(0, n);
    m = 0;
    for (int i = 0; i < n; i++) {
        t[m++] = '#';
        t[m++] = s[i];
    }
    t[m++] = '$';
    t[0] = '^';
    manacher();
    ll ans = 0;
    for (int i = 1; i < m-1; i++) {
        int k = p[i];
        if (t[i-k] == '#') k--;
        for(; k >= 0; k -= 2) {
            int start = sai[i-k>>1];
            int mino = node_minocc(root,k+1,start);
            ll hsh = k*(n+1LL)+mino;
            if (found.find(hsh) != found.end()) {
                break;
            }
            found.insert(hsh);
            int maxo = node_maxocc(root,k+1,start+1);
            ll c = maxo - mino;
            ans += c*(c-1);
            ans %= mod;
        }
    }
    ans = ans * (mod+1>>1) % mod;
    printf("%lld\n", ans);
}

Palindromic Border C Sharp Solution

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;

class Solution {

    /*
     * Complete the palindromicBorder function below.
     */
    static int palindromicBorder(string s) {
        
        int m = 1000000007;

        GetPalindromeFrequencies(s, out TreeNode oddBaseNode, out TreeNode evenBaseNode);

        return (int)((oddBaseNode.SumFrequencyShit(m) + evenBaseNode.SumFrequencyShit(m)) % m);
    }

    public static int palindromicBorder2(string s)
    {
        if (s.Length <= 1)
            return 0;

        Manacher2(s, out var even, out var odd);
        odd.CascadeFrequenciesDown();
        even.CascadeFrequenciesDown();

        even.Frequency = 0;
        even.GetNext(0).Frequency = 0;
        odd.Frequency = 0;

        long m = 1000000007;


        long result = (odd.GetCount(2 * m, false, false) + even.GetCount(2 * m, false, true)) / 2 % m;
        return (int) result;
    }

    class TreeNode
    {
        public int Frequency;
        public TreeNode[] NextNodes;

        public long SumFrequencyShit(long m)
        {
            long result = (long)Frequency * ((long)Frequency - 1) / 2 % m;
            if (NextNodes == null)
                return result;
            for (int i = 0; i < NextNodes.Length; i++)
            {
                var node = NextNodes[i];
                if (node != null)
                {
                    result = (result + node.SumFrequencyShit(m)) % m;
                }
            }
            return result;
        }
    }

    static void GetPalindromeFrequencies(string s, out TreeNode oddBaseNode, out TreeNode evenBaseNode)
    {
        int[] letters = new int[s.Length];
        for (int i = 0; i < s.Length; i++)
        {
            letters[i] = (int)(s[i] - 'a');
        }

        oddBaseNode = new TreeNode();
        oddBaseNode.NextNodes = new TreeNode[8];
        evenBaseNode = new TreeNode();
        evenBaseNode.NextNodes = new TreeNode[8];
        for (int i = 0; i < letters.Length; i++)
        {
            var node = oddBaseNode.NextNodes[letters[i]];
            if (node == null)
            {
                node = new TreeNode();
                oddBaseNode.NextNodes[letters[i]] = node;
            }
            node.Frequency++;
            int max = Math.Min(i, letters.Length - i - 1);
            for (int j = 1; j <= max; j++)
            {
                int start = i - j;
                int end = i + j;
                if (letters[start] == letters[end])
                {
                    if (node.NextNodes == null)
                    {
                        node.NextNodes = new TreeNode[8];
                    }
                    var nextNode = node.NextNodes[letters[start]];
                    if (nextNode == null)
                    {
                        nextNode = new TreeNode();
                        node.NextNodes[letters[start]] = nextNode;
                    }
                    node = nextNode;
                    node.Frequency++;
                }
                else
                {
                    break;
                }
            }
            node = evenBaseNode.NextNodes[letters[i]];
            if (node == null)
            {
                node = new TreeNode();
                evenBaseNode.NextNodes[letters[i]] = node;
            }
            max = Math.Min(i + 1, letters.Length - i - 1);
            for (int j = 1; j <= max; j++)
            {
                int start = i - j + 1;
                int end = i + j;
                if (letters[start] == letters[end])
                {
                    if (node.NextNodes == null)
                    {
                        node.NextNodes = new TreeNode[8];
                    }
                    var nextNode = node.NextNodes[letters[start]];
                    if (nextNode == null)
                    {
                        nextNode = new TreeNode();
                        node.NextNodes[letters[start]] = nextNode;
                    }
                    node = nextNode;
                    node.Frequency++;
                }
                else
                {
                    break;
                }    
            }
        }
    }




    class TreeNode2
    {
        public long Frequency = 0;

        TreeNode2[] nextNodes = new TreeNode2[9];

        public TreeNode2 Parent;

        public TreeNode2 GetNext(int i)
        {
            var node = nextNodes[i];

            if (node == null)
            {
                node = new TreeNode2();
                node.Parent = this;
                nextNodes[i] = node;
            }

            return node;
        }

        public TreeNode2 GetParent(int depth)
        {
            if (depth == 0)
                return this;
            else
                return Parent.GetParent(depth - 1);
        }

        public long GetCount(long m, bool isEven, bool shouldSkip)
        {
            long result = 0;
            for (int i = 0; i < nextNodes.Length; i++)
            {
                var node = nextNodes[i];
                if (node != null)
                {
                    long count = node.GetCount(m, isEven, !shouldSkip);
                    result = (result + count) % m;
                }
            }

            if (isEven)
            {
                if (shouldSkip)
                {
                    return result;
                }
                else
                {
                    return (result + Frequency * (Frequency - 1) / 8) % m;
                }
            }
            else
            {
                return (result + Frequency * (Frequency - 1) / 2) % m;
            }

        }

        public void CascadeFrequenciesDown()
        {
            for (int i = 0; i < nextNodes.Length; i++)
            {
                var node = nextNodes[i];
                if (node != null)
                {
                    node.CascadeFrequenciesDown();
                    Frequency += node.Frequency;
                }
            }
        }

        public string Name;
        public void SetName(string s)
        {
            Name = s;
            for (int i = 0; i < nextNodes.Length; i++)
            {
                var node = nextNodes[i];
                if (node != null)
                {
                    if (s.Length == 0)
                        node.SetName(i.ToString());
                    else
                        node.SetName(i + s + i);
                }
            }
        }

        public override string ToString() => Name ?? "";
    }

    static int[] Manacher2(string s, out TreeNode2 evenBaseNode, out TreeNode2 oddBaseNode)
    {
        return Manacher2(ToInts(s), out evenBaseNode, out oddBaseNode);
    }

    static int[] Manacher2(int[] s, out TreeNode2 evenBaseNode, out TreeNode2 oddBaseNode)
    {
        int[] result = new int[s.Length];

        TreeNode2[] treeNodes = new TreeNode2[s.Length];

        oddBaseNode = new TreeNode2();
        evenBaseNode = new TreeNode2();

        int c = 0;
        int r = 0;
        int m = 0;
        int n = 0;

        treeNodes[0] = evenBaseNode.GetNext(s[0]);
        treeNodes[0].Frequency++;

        for (int i = 1; i < s.Length; i++)
        {
            treeNodes[i] = (i % 2 == 0 ? evenBaseNode : oddBaseNode).GetNext(s[i]);
            treeNodes[i].Frequency++;
            if (i > r)
            {
                result[i] = 0;
                m = i - 1;
                n = i + 1;
            }
            else
            {
                int j = 2 * c - i;
                if (result[j] <= r - i - 1)
                {
                    result[i] = result[j];
                    treeNodes[i].Frequency--;
                    treeNodes[i] = treeNodes[j];
                    treeNodes[i].Frequency++;
                    m = -1;
                }
                else
                {
                    result[i] = r - i;

                    treeNodes[i].Frequency--;
                    treeNodes[i] = treeNodes[j].GetParent(result[j] - result[i]);
                    treeNodes[i].Frequency++;


                    n = r + 1;
                    m = 2 * i - n;
                }
            }

            while (m >= 0 && n < s.Length && s[m] == s[n])
            {
                result[i]++;

                treeNodes[i].Frequency--;
                treeNodes[i] = treeNodes[i].GetNext(s[m]);
                treeNodes[i].Frequency++;
                m--;
                n++;
            }

            if (i + result[i] > r)
            {
                c = i;
                r = i + result[i];
            }
        }

        return result;
    }


    static int[] ToInts(string s)
    {
        int[] result = new int[s.Length * 2 + 1];

        for (int i = 0; i < s.Length; i++)
        {
            result[2 * i + 1] = (int) (s[i] - 'a' + 1);
        }
        return result;
    }

    static void Main(string[] args) {
        TextWriter textWriter = new StreamWriter(@System.Environment.GetEnvironmentVariable("OUTPUT_PATH"), true);

        string s = Console.ReadLine();

        int result = palindromicBorder2(s);

        textWriter.WriteLine(result);

        textWriter.Flush();
        textWriter.Close();
    }
}

Palindromic Border Java Solution

import java.io.*;
import java.util.Arrays;

public class timus2040 {

    static int[][] es;
    static int[] slink, len, cnt;
    static int free;

    static int newNode(int l) {
        len[free] = l;
        return free++;
    }

    static int get(int i, char c) {
        return es[c - 'a'][i];
    }

    static void set(int i, char c, int n) {
        es[c - 'a'][i] = n;
    }

    public static void solve(Input in, PrintWriter out) throws IOException {
        char[] s = in.next().toCharArray();
        int n = s.length;
        es = new int[8][n + 2];
        for (int[] ar : es) {
            Arrays.fill(ar, -1);
        }
        len = new int[n + 2];
        slink = new int[n + 2];
        cnt = new int[n + 2];
        int root0 = newNode(0);
        int rootm1 = newNode(-1);
        slink[root0] = slink[rootm1] = rootm1;
        int cur = root0;
        for (int i = 0; i < n; ++i) {
            while (i - len[cur] == 0 || s[i] != s[i - len[cur] - 1]) {
                cur = slink[cur];
            }
            if (get(cur, s[i]) == -1) {
                set(cur, s[i], newNode(len[cur] + 2));
                if (cur == rootm1) {
                    slink[get(cur, s[i])] = root0;
                } else {
                    int cur1 = slink[cur];
                    while (s[i] != s[i - len[cur1] - 1]) {
                        cur1 = slink[cur1];
                    }
                    slink[get(cur, s[i])] = get(cur1, s[i]);
                }
            }
            cur = get(cur, s[i]);
            cnt[cur]++;
        }
        long ans = 0;
        for (int i = free - 1; i >= 0; --i) {
            cnt[slink[i]] += cnt[i];
            if (len[i] > 0) {
                ans = (ans + 1L * cnt[i] * (cnt[i] - 1) / 2) % 1000000007;
            }
        }
        out.println(ans);
    }

    public static void main(String[] args) throws IOException {
//        FileWriter out = new FileWriter("output.txt");
//        solve(new FileReader("input.txt"), out);
        PrintWriter out = new PrintWriter(System.out);
        solve(new Input(new BufferedReader(new InputStreamReader(System.in))), out);
        out.close();
    }

    static class Input {
        BufferedReader in;
        StringBuilder sb = new StringBuilder();

        public Input(BufferedReader in) {
            this.in = in;
        }

        public Input(String s) {
            this.in = new BufferedReader(new StringReader(s));
        }

        public String next() throws IOException {
            sb.setLength(0);
            while (true) {
                int c = in.read();
                if (c == -1) {
                    return null;
                }
                if (" \n\r\t".indexOf(c) == -1) {
                    sb.append((char)c);
                    break;
                }
            }
            while (true) {
                int c = in.read();
                if (c == -1 || " \n\r\t".indexOf(c) != -1) {
                    break;
                }
                sb.append((char)c);
            }
            return sb.toString();
        }

        public int nextInt() throws IOException {
            return Integer.parseInt(next());
        }

        public long nextLong() throws IOException {
            return Long.parseLong(next());
        }

        public double nextDouble() throws IOException {
            return Double.parseDouble(next());
        }
    }
}

Palindromic Border JavaScript Solution

'use strict';

const fs = require('fs');

process.stdin.resume();
process.stdin.setEncoding('utf-8');

let inputString = '';
let currentLine = 0;

process.stdin.on('data', inputStdin => {
    inputString += inputStdin;
});

process.stdin.on('end', _ => {
    inputString = inputString.trim().split('\n').map(str => str.trim());

    main();
});

function readLine() {
    return inputString[currentLine++];
}

/*
 * Complete the palindromicBorder function below.
 */
function palindromicBorder(str) {
  const counter = {
    count: 0,
    devidedBy: 1e9 + 7,
    add (count) {
      this.count = this.count + count
      if (this.count >= this.devidedBy) this.count %= this.devidedBy
    }
  }
  const newBorderState = (border, j=0, k=1) => ({border: border, j: j, k: k, indices: []})
  const kinds = []
  const borderStateMap = {}
  'abcdefgh'.split('').forEach(char => {
    borderStateMap[char] = newBorderState(char)
    if (str.indexOf(char) !== -1) kinds.push(char)
  })
  
  if (kinds.length === 1) {
    const len = str.length
    counter.add(len * (len + 1) * (len - 1) / 6)
    return counter.count
  }
  
  for (let i=0; i < str.length; i++) {
    borderStateMap[str[i]].indices.push(i)
  }
  
  
  
  
  
  const borderStateArray = []
  for (const char of Object.keys(borderStateMap)) {
    let j = borderStateMap[char].j
    let alive = borderStateMap[char].indices
    delete borderStateMap[char]
    while (alive.length) {
      const i = alive[0]
      while (i === alive[0]) {
        const prevBorder = str.slice(i, i+j)
        const borderState = newBorderState(prevBorder, j-1)
        alive = alive.filter(l => {
          if (str[l+j] === char) return true
          else if (str[l+j]) return void borderState.indices.push(l)
          else return false
        })
        counter.add(alive.length * (alive.length - 1) / 2)
        if (borderState.indices.length) borderStateArray.push(borderState)
        j++
      }
    }
  }
  
  
  while (borderStateArray.length) {
    const index = borderStateArray.length-1
    const j = borderStateArray[index].j
    let k = borderStateArray[index].k
    let alive = borderStateArray[index].indices
    borderStateArray.pop()
    while (alive.length) {
      const i = alive[0]
      while (i === alive[0]) {
        const char = str[i+j+k]
        const prevBorder = str.slice(i-k+1, i+j+k-1)
        const borderState = newBorderState(prevBorder, j, k)
        alive = alive.filter(l => {
          const curr0 = str[l-k]
          const curr1 = str[l+j+k]
          if (!curr1) return false
          else if (curr0 === char && curr1 === char) return true
          else if (curr0 === curr1) return void borderState.indices.push(l)
          else return false
        })
        counter.add(alive.length * (alive.length - 1) / 2)
        if (borderState.indices.length) borderStateArray.push(borderState)
        k++
      }
    }
  }
  return counter.count
}


function main() {
    const ws = fs.createWriteStream(process.env.OUTPUT_PATH);

    const s = readLine();

    let result = palindromicBorder(s);

    ws.write(result + "\n");

    ws.end();
}

Palindromic Border Python Solution

def mod(x):
    return x % 1000000007

class trie(object):
    def __init__(self, depth=0, parent=None, data=None):
        self.count = 0
        self.depth = depth
        self.parent = parent
        self.data = data
        self.next = {}
        
    def get(self, char):
        if char in self.next:
            return self.next[char]
        ans = trie(self.depth + 2, self, char)
        self.next[char] = ans
        return ans
    
    def children(self):
        return self.next.values()

def dfs(node):
    ans = 0
    stack = []
    stack.append((node, True))
    while len(stack) > 0:
        node, extend = stack.pop()
        if extend:
            stack.append((node, False))
            for child in node.children():
                stack.append((child, True))
        else:
            for child in node.children():
                node.count += child.count
            if node.depth > 0:
                ans = mod(ans + mod(node.count * (node.count - 1) // 2))
    return ans

def pr(node):
    print(' ' * node.depth + '%s (%d:%d)' % (chr(node.data) if node.data else ' ', node.depth, node.count))
    for child in node.children():
        pr(child)

def score(string):
    # ascii values
    string = list(map(ord, string))
    N = len(string)*2 + 1
    c = [0] * N
    c[1::2] = string
    # initialize trie pointers
    odd = trie(depth = -1)
    even = trie()
    center, radius = 0, 0
    left, right = 0, 0
    # manacher's algorithm
    node = [even]
    span = [0]
    for i in range(1, N):
        if i > radius:
            node.append(odd.get(c[i]) if (i & 1) else even)
            span.append(0)
            left = i - 1
            right = i + 1
        else:
            mirror = center * 2 - i
            if span[mirror] < radius - i:
                span.append(span[mirror])
                node.append(node[mirror])
                left = -1
            else:
                span.append(radius - i)
                node.append(node[mirror])
                while node[i].depth > radius - i:
                    node[i] = node[i].parent
                right = radius + 1
                left = i * 2 - right
        while left >= 0 and right < N and c[left] == c[right]:
            if c[right]:
                node[i] = node[i].get(c[right])
            span[i] += 1
            left -= 1
            right += 1
        node[i].count += 1
        if i + span[i] > radius:
            center = i
            radius = i + span[i]
    # accumulate count
    return mod(dfs(odd) + dfs(even))
    
print(score(str(input())))
c C# C++ HackerRank Solutions java javascript python

Leave a Reply