In this post, we will solve HackerRank Similar Strings Problem Solution.
Jimmy loves playing with strings. He thinks string A is similar to string B if the following conditions are satisfied:
- Both strings have the same length (i.e., A = a0a1 ..an-1 and B bob₁…bn-1). =
- For each valid pair of indices, (i, j), in the strings, [a; = aj and b; = b;] or [a; a; and
bi #bj].
For example, string a = “adba” and b = “bcgb” are similar as for i = 0, j = 3, a[0] == a[3] and b[0] == b[3] and for all other i, j pairs a[i] # a[j] as well as b[i] # b[j]. He has a string, S. of size n and gives you a queries to answer where each query is in the form of a pair of integers (li,r). For each substring S[li, ri], find the number of substrings S[x, y] where substring S[l, ri] is similar to substring S[x, y] and print this number on a new line.
Note: Substring S[x, y] is the contiguous sequence of characters from index a to index y. For example, if S = abcdefgh, then S[3,6] = cdef.
Input Format
The first line contains two space-separated integers describing the respective values of n and q.
The second line contains string S.
Each line i of the & subsequent lines contains two space-separated integers describing the
respective values of l; and r; for query i.
Output Format
For each query, print the number of similar substrings on a new line.
Sample Input
8 4
giggabaj
1 1
1 2
1 3
2 4
Sample Output
8
6
2
1
Explanation
We perform the following sequence of queries:
- Strings with length 1 are all similar, so our answer is 8.
gi
,ig
,ga
,ab
,ba
, andaj
are similar, so our answer is 6.gig
andaba
are similar, so our answer is 2.igg
has no similar string, so our answer is 1.

Similar Strings C Solution
#include <stdio.h>
#include <malloc.h>
#define rint register int
typedef unsigned short ushort;
char* TVA;
char* S;
int n;
int cmpPos(const void*pa,const void*pb){
rint a = *((ushort*)pa);
rint b = *((ushort*)pb);
int r = 1;
if(a>b){
r = a;
a = b;
b = r;
r = -1;
}
char* VA = TVA+ a*10;
char* VB = TVA + b*10;
for(;b<n;a++,b++){
int dr = (int)VA[S[a]] - (int)VB[S[b]];
if(dr) return dr*r;
}
return r;
}
inline int sameLen(int pa,int pb){
rint a = pa;
rint b = pb;
if(a>b){
a ^= b;
b ^= a;
a ^= b;
}
pa = a;
char* VA = TVA+a*10;
char* VB = TVA+b*10;
for(;b<n;a++,b++)
if(VA[S[a]] != VB[S[b]]) return a - pa;
return a-pa;
}
int main(void) {
int q;
scanf("%d %d",&n,&q);
S = (char*)malloc(sizeof(char)*(n+1));
scanf("%s",S);
S[n] = -1;
for(rint i=0;i<n;i++) S[i] -= 'a';
TVA = (char*)malloc(sizeof(char)*(n+1)*10);
for(rint i =0;i<10;i++) TVA[i+(n)*10] = i;
for(rint i=n-1;i>=0;i--){
char* TVAi = TVA + i*10;
char sip = TVAi[S[i]+10];
for(rint j=0;j<10;j++){
if(TVAi[j+10] < sip) TVAi[j] = TVAi[j+10] + 1;
else TVAi[j] = TVAi[j+10];
}
TVAi[S[i]] = 0;
}
ushort* SA = (ushort*)malloc(sizeof(ushort)*n);
for(rint i=0;i<n;i++) SA[i] = (ushort)i;
qsort(SA,n,sizeof(ushort),cmpPos);
ushort* SB = (ushort*)malloc(sizeof(ushort)*n);
ushort* KB = (ushort*)malloc(sizeof(ushort)*n);
for(rint i=1;i<n;i++){
SB[i] = sameLen(SA[i-1],SA[i]);
KB[SA[i]] = i;
}
for(int w=0;w<q;w++){
int x,y;
scanf("%d %d",&x,&y);
int d = y - x + 1;
rint tx = KB[x-1];
while(tx>0 && SB[tx]>=d) tx--;
rint ty = KB[x-1]+1;
while(ty<n && SB[ty]>=d) ty++;
printf("%d\n",ty-tx);
}
return 0;
}
Similar Strings C++ Solution
#include <bits/stdc++.h>
#define mo(x) ((x)<P?(x):(x)-P)
using namespace std;
const int N=100009;
const int C=10;
const long long P=pow(10,9)+97;
int n,m;
char c[N*2];
int a[N][C],v[N],v2[N];
long long b[N][C],p[N];
void input(){
scanf("%d%d",&n,&m);
assert(1<=min(n,m)&& max(n,m)<=50000);
scanf("%s",c+1);
}
int getmax(int x,int y){
if (x>y) swap(x,y);
int r=n-y+1;
int l=0,mi,h=0;
while (l<r){
mi=(l+r+1)/2;
h=0;
for (int i=0;h==i && i<C;i++)
h+=(((b[x+mi-1][a[x][i]]
-b[x -1][a[x][i]])*p[y-x]
-b[y+mi-1][a[y][i]]
+b[y -1][a[y][i]])%P==0);
if (h==C) l=mi; else r=mi-1;
}
return l;
}
bool sufcomp(int x,int y){
int d=getmax(x,y);
if (d==n-max(x,y)+1)
return x>y;
int _A=0,_B=0;
for (int i=0;i<C;i++){
if (c[x+d]==a[x][i]) _A=i;
if (c[y+d]==a[y][i]) _B=i;
}
return _A<_B;
}
void pre(){
p[0]=1;
for (int i=1;i<N;i++) p[i]=p[i-1]*5021%P;
for (int i=1;i<=n;i++) c[i]-='a';
for (int i=0;i<C;i++) a[n+1][i]=i;
for (int i=n;i>0;i--){
int I=0;
for (int j=0;j<C;j++){
a[i][j]=a[i+1][j];
if (a[i][j]==c[i]) I=j;
}
while (I--) swap(a[i][I],a[i][I+1]);
}
for (int i=1;i<=n;i++){
b[i][c[i]]=p[i];
for (int j=0;j<C;j++)
b[i][j]=mo(b[i][j]+b[i-1][j]);
}
for (int i=1;i<=n;i++) v[i]=i;
stable_sort(v+1,v+n+1,sufcomp);
for (int i=1;i<=n;i++) v2[v[i]]=i;
}
void sol(){
pre();
while (m--){
int l,r,mi;
scanf("%d%d",&l,&r);
int x=v2[l];
int d=r-l+1;
l=1;
r=x;
while (l<r){
mi=(l+r)/2;
if (getmax(v[x],v[mi])<d)
l=mi+1;
else
r=mi;
}
int L=l;
l=x;
r=n;
while (l<r){
mi=(l+r+1)/2;
if (getmax(v[x],v[mi])<d)
r=mi-1;
else
l=mi;
}
int R=l;
printf("%d\n",R-L+1);
}
}
int main() {
input();
sol();
return 0;
}
Similar Strings C Sharp Solution
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;
class Solution {
static int n;
static int[] s;
static int[][] firstOccurrence;
static Node[] nodes;
static void Main(String[] args) {
/* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution */
int[] input = Console.ReadLine().Split().Select(item => int.Parse(item)).ToArray();
n = input[0];
int q = input[1];
// keep track of appearances of each letter
int[] previousOccurrence = new int[26];
firstOccurrence = new int[n][];
firstOccurrence[0] = new int[26];
for (int i = 0; i < 26; i++)
{
firstOccurrence[0][i] = -1;
previousOccurrence[i] = -1;
}
// each letter points to the next occurrance of the same letter
int[] nextOccurrence = new int[n];
int currentIndex = 0;
s = Console.ReadLine().Select(c => c - 'a').ToArray();
foreach (int c in s)
{
if (previousOccurrence[c] != -1)
{
nextOccurrence[previousOccurrence[c]] = currentIndex;
}
if (firstOccurrence[0][c] == -1)
{
firstOccurrence[0][c] = currentIndex;
}
previousOccurrence[c] = currentIndex;
currentIndex++;
}
// Populate mapping array for each prefix
// to be used in comparisons
for (int i = 1; i < n; i++)
{
firstOccurrence[i] = new int[26];
for (int j = 0; j < 26; j++)
{
firstOccurrence[i][j] = firstOccurrence[i - 1][j] - 1;
}
firstOccurrence[i][s[i - 1]] = nextOccurrence[i - 1] - i;
}
nodes = new Node[n];
Trie t = new Trie();
for (int i = 1; i < n; i++)
{
t.Insert(i);
}
StringBuilder output = new StringBuilder();
for (int i = 0; i < q; i++)
{
input = Console.ReadLine().Split().Select(item => int.Parse(item)).ToArray();
int l = input[0] - 1;
int r = input[1] - 1;
int length = r - l + 1;
int count;
if (length == 1)
{
count = n;
}
else
{
Node prefixNode = nodes[l];
while ((prefixNode.Parent != null) && (prefixNode.Parent.Length >= length))
{
prefixNode = prefixNode.Parent;
}
count = prefixNode.Count;
}
output.Append(count);
output.AppendLine();
}
Console.WriteLine(output.ToString());
}
public class Node
{
public int PrefixId;
public int StartIndex;
public int EndIndex;
public int Count;
public int Length;
public Node Parent;
public Dictionary<int, Node> Children;
}
public class Trie
{
private Node _root;
public Trie()
{
_root = new Node()
{
PrefixId = 0,
StartIndex = 0,
EndIndex = n - 1,
Count = 1,
Length = n,
Parent = null
};
nodes[0] = _root;
}
public void Insert(int insertPrefixId)
{
Node lookupNode = _root;
Node insertNode = new Node()
{
PrefixId = insertPrefixId,
Count = 1,
EndIndex = n - 1,
Length = n - insertPrefixId
};
nodes[insertPrefixId] = insertNode;
int[] firstOccurrenceInInsertNode = firstOccurrence[insertPrefixId];
int insertFirstIndex = 0;
int insertCurrentIndex = insertPrefixId;
while (true)
{
int lookupFirstIndex = 0;
int lookupCurrentIndex;
int[] firstOccurrenceInLookupNode = firstOccurrence[lookupNode.PrefixId];
insertCurrentIndex++;
for (lookupCurrentIndex = lookupNode.StartIndex + 1;
lookupCurrentIndex <= lookupNode.EndIndex;
lookupCurrentIndex++, insertCurrentIndex++)
{
lookupFirstIndex = firstOccurrenceInLookupNode[s[lookupCurrentIndex]];
if (insertCurrentIndex > insertNode.EndIndex)
{
insertFirstIndex = -1;
}
else
{
insertFirstIndex = firstOccurrenceInInsertNode[s[insertCurrentIndex]];
if (insertFirstIndex == lookupFirstIndex)
{
continue;
}
}
// Split Current Node into two
Node siblingNode = new Node()
{
Parent = lookupNode,
PrefixId = lookupNode.PrefixId,
StartIndex = lookupCurrentIndex,
EndIndex = lookupNode.EndIndex,
Count = lookupNode.Count,
Length = lookupNode.Length,
Children = lookupNode.Children
};
if (siblingNode.Children != null)
{
foreach (Node nephews in siblingNode.Children.Values)
{
nephews.Parent = siblingNode;
}
}
else
{
nodes[lookupNode.PrefixId] = siblingNode;
}
insertNode.Parent = lookupNode;
insertNode.StartIndex = insertCurrentIndex;
lookupNode.Count++;
lookupNode.Length = lookupNode.Length - (lookupNode.EndIndex - (lookupCurrentIndex - 1));
lookupNode.EndIndex = lookupCurrentIndex - 1;
lookupNode.Children = new Dictionary<int, Node>();
lookupNode.Children.Add(lookupFirstIndex, siblingNode);
lookupNode.Children.Add(insertFirstIndex, insertNode);
return;
}
Node nextLookupNode = null;
insertFirstIndex = (insertCurrentIndex > insertNode.EndIndex) ? -1 : firstOccurrenceInInsertNode[s[insertCurrentIndex]];
if (lookupNode.Children == null)
{
lookupNode.Children = new Dictionary<int, Node>();
break;
}
if (!lookupNode.Children.TryGetValue(insertFirstIndex, out nextLookupNode))
{
break;
}
lookupNode.Count++;
lookupNode = nextLookupNode;
}
// Insert new node
insertNode.Parent = lookupNode;
insertNode.StartIndex = insertCurrentIndex;
lookupNode.Children.Add(insertFirstIndex, insertNode);
lookupNode.Count++;
return;
}
}
}
Similar Strings Java Solution
import java.io.*;
import java.math.*;
import java.text.*;
import java.util.*;
import java.util.regex.*;
public class Solution {
static final int NUM_CHARS = 11;
static final int ENCODE_LENGTH = 85;
static long encode(final char[] chars, final int start, final int checkLength) {
final int length = Math.min(checkLength, chars.length-1);
long hash = 31;//5381;
int[] sim = new int[NUM_CHARS];
int count = 1;
int i=start;
for(; i <= start+length && i < chars.length; i++) {
int sim_index = chars[i] - 'a';
if(sim[sim_index] == 0) {
sim[sim_index] = count;
count++;
}
hash = hash * sim[sim_index] + 33;
}
return hash;
}
static Map<Long, List<Integer>> buildIndex(final char[] chars) {
Map<Long, List<Integer>> index = new HashMap<>();
for(int i = 0; i < chars.length - ENCODE_LENGTH; i++) {
final long encoded = encode(chars, i, ENCODE_LENGTH);
List<Integer> indexes = index.get(encoded);
if(indexes == null) {
indexes = new LinkedList<>();
index.put(encoded, indexes);
}
indexes.add(i);
}
return index;
}
static boolean isSimilar(final char[] chars, final int aStart, final int aEnd, final int bOffset) {
final int checkLength = aEnd - aStart + 1;
int[] simI = new int[NUM_CHARS+1];
int[] simJ = new int[NUM_CHARS+1];
for(int i=0; i < checkLength; i++) {
int indexI = chars[i+aStart] - 'a' + 1;
int indexJ = chars[i+bOffset] - 'a' + 1;
if(simI[indexI] == 0 && simJ[indexJ] == 0) {
simI[indexI] = indexJ;
simJ[indexJ] = indexI;
} else if(simI[indexI] != indexJ || simJ[indexJ] != indexI)
return false;
}
return true;
}
/*
* Complete the similarStrings function below.
*/
static int similarStrings(final char[] chars, int start, int end, Map<Long, List<Integer>> charIndex) {
final int sLength = chars.length;
final int checkLength = end - start + 1;
int answer = 0;
if(checkLength == 1)
answer = sLength;
else if(checkLength == ENCODE_LENGTH) {
List<Integer> indexes = charIndex.get(encode(chars,start-1, ENCODE_LENGTH));
answer = indexes == null ? 1 : indexes.size();
} else if(checkLength < ENCODE_LENGTH) {
for(int index=0; index <= sLength - checkLength; index++)
if(index == start-1 ||
isSimilar(chars, start-1, end-1, index))
answer++;
} else {
List<Integer> indexes = charIndex.get(encode(chars,start-1,ENCODE_LENGTH));
if(indexes == null)
answer = 1;
else {
for(Integer index : indexes) {
if(index + checkLength > chars.length) {
break;
} else if(index == start-1 ||
isSimilar(chars, start-1, end-1, index))
answer++;
}
}
if(answer == 0)
answer = 1;
}
return answer;
}
public static void main(String[] args) throws IOException {
final Scanner input = new Scanner(System.in);
String[] nq = input.nextLine().split(" ");
final int n = Integer.parseInt(nq[0].trim());
final int q = Integer.parseInt(nq[1].trim());
final String s = input.nextLine().trim();
final char[] sChars = s.toCharArray();
final Map<Long, List<Integer>> index = buildIndex(sChars);
StringBuilder answer = new StringBuilder(q*3);
for (int queriesRowItr = 0; queriesRowItr < q; queriesRowItr++) {
final int l = input.nextInt();
final int r = input.nextInt();
final int result = similarStrings(sChars, l, r, index);
answer.append(result);
answer.append('\n');
}
System.out.print(answer.toString());
input.close();
}
}
Similar Strings JavaScript Solution
process.stdin.resume();
process.stdin.setEncoding('ascii');
var input_stdin = "";
var input_stdin_array = [];
var input_currentline = 0;
process.stdin.on('data', function (data) {
input_stdin += data;
});
process.stdin.on('end', function () {
input_stdin_array = input_stdin.split("\n");
main();
});
function readLine() {
return input_stdin_array[input_currentline++];
}
/////////////// ignore above this line ////////////////////
//var MAX_TREE_LEVEL = 50;
// Build a flat dictionary
function getDictionary(str, len) {
var dictionary = [],
i, j, k, n, c;
for (i = 0; i < len; ++i) {
n = 0;
j = i;
k = i * 10;
while(n < 10 && j < len) {
c = str[j++];
if (null == dictionary[k + c]) {
dictionary[k + c] = n++;
}
}
}
return dictionary;
}
function strToNums(input) {
var str = [];
for (var i = 0, len = input.length; i < len; ++i) {
str.push(input.charCodeAt(i) - 97);
}
return str;
}
function buildTree(str, len, dictionary) {
var root = [],
node,
current, next, index, c, i, j;
for (i = 0; i < len; ++i) {
current = root;
for (j = i + 1; j < len; ++j) {
c = str[j];
index = dictionary[c + i * 10];
current = current[index] || (current[index] = (node = [], node[10] = 0, node));
++current[10];
if (j - i > 50) {
(current[11] = current[11] || []).push(i);
break;
}
}
}
return root;
}
function query(tree, dictionary, str, len, li, ri) {
if (1 === ri - li) {
return len;
}
var current = tree,
node, positions, i;
for (i = li + 1; i < ri; ++i) {
node = current[dictionary[str[i] + li * 10]];
if (!node) {
if (!(positions = current[11])) {
return 1;
}
return naiveCount(str, len, dictionary, positions, li, ri);
}
if (1 === node[10]) {
return 1;
}
current = node;
}
return current[10];
}
function naiveCount(str, len, dictionary, positions, li, ri) {
var count = 0,
offset2 = li * 10,
start = li + 50,
pos, pLen, i;
for (i = 0, pLen = positions.length; i < pLen; ++i) {
pos = positions[i];
if (pos === li || (pos + ri - li <= len && match(str, dictionary, pos - li, start, ri, pos * 10, offset2))) {
++count;
}
}
return count;
}
function match(str, dictionary, pos, start, end, offset1, offset2) {
for (var j = start; j < end; ++j) {
if (dictionary[str[pos + j] + offset1] !== dictionary[str[j] + offset2]) {
return false;
}
}
return true;
}
function main() {
var tests = +readLine().split(' ')[1],
str = strToNums(readLine()),
len = str.length,
dictionary = getDictionary(str, len),
tree = buildTree(str, len, dictionary),
stdout = process.stdout,
input, i
for (i = 0; i < tests; ++i) {
input = readLine().split(' ');
stdout.write(query(tree, dictionary, str, len, (input[0] | 0) - 1, (input[1] | 0)) + "\n");
}
}
Similar Strings Python Solution
#!/bin/python3
import math
import os
import random
import re
import sys
#
# Complete the 'similarStrings' function below.
#
# The function is expected to return an INTEGER_ARRAY.
# The function accepts following parameters:
# 1. INTEGER n
# 2. 2D_INTEGER_ARRAY queries
#
def extract_map2(subst):
pairs_ = []
len_ = len(subst)
follow_map = 0
for s in range(len_-1):
if follow_map & 1 == 0:
follow_map >>= 1
s_pairs_ = 0b0
index = 0
for e in range(s + 1, len_):
if subst[s] == subst[e]:
s_pairs_ += 1 << index
index += 1
follow_map |= s_pairs_
pairs_.append([s, s_pairs_])
else:
follow_map >>= 1
return pairs_
# def extract_map(subst):
# len_ = len(subst)
# pairs_ = [0 for i in range(len_ - 1)]
# follow_map = 0
# for s in range(len_-1):
# if follow_map & 1 == 0:
# follow_map >>= 1
# s_pairs_ = 0b0
# index = 0
# for e in range(s + 1, len_):
# if subst[s] == subst[e]:
# s_pairs_ += 1 << index
# if e != len_:
# pairs_[e] = s
# index += 1
# follow_map |= s_pairs_
# pairs_[s] = s_pairs_
# else:
# follow_map >>= 1
# pairs_[s] = pairs_[ pairs_[s] ] >> s
# return pairs_
def extract_map(subst):
pairs_ = []
len_ = len(subst)
for s in range(len_-1):
s_pairs_ = 0b0
index = 0
for e in range(s + 1, len_):
if subst[s] == subst[e]:
s_pairs_ += 1 << index
index += 1
pairs_.append(s_pairs_)
return pairs_
def extract_submap(map_, s, e):
pairs_ = []
len_ = e - s - 1
mask = 2 ** len_ - 1
for s_ in range(s, e - 1):
pairs_.append( map_[s_] & mask )
mask >>= 1
return pairs_
def similarStrings(n, queries):
# Write your code here
out = []
s_map = extract_map(n)
s_len = len(n)
for s, e in queries:
ss_map = extract_submap(s_map, s - 1, e)
ss_len = e - s + 1
sss_len = s_len
if ss_len > 1:
candidates = list(range(s_len - ss_len + 1))
len_ = ss_len - 1
mask = 2 ** len_ - 1
for s_ in ss_map:
candidates = [
st + 1 \
for st in candidates \
if s_map[st] & mask == s_
]
mask >>= 1
sss_len = len(candidates)
out.append(sss_len)
return out
if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')
first_multiple_input = input().rstrip().split()
n = int(first_multiple_input[0])
q = int(first_multiple_input[1])
queries = []
n = str(input().strip())
for _ in range(q):
queries.append(list(map(int, input().rstrip().split())))
result = similarStrings(n, queries)
fptr.write('\n'.join(map(str, result)))
fptr.write('\n')
fptr.close()