HackerRank Palindromic Border Problem Solution Yashwant Parihar, May 2, 2023May 2, 2023 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 countsubstrings 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 FormatThe first line contains a string consisting of N characters.Output FormatPrint 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 ExplanationS = ababa has 15 substrings but only 4 substrings have palindromic borders.S1…3 aba P (S1…3)=1S1…5 ababa P (S1…5) = 2 S2…4 bab P (S2…4) = 1S3…5 aba P(S3…5)=1 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 CcppCSharpHackerrank Solutionsjavajavascriptpython