HackerRank Similar Strings Problem Solution

Yashwant Parihar,

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:

  1. Strings with length 1 are all similar, so our answer is 8.
  2. gi, ig, ga, ab, ba, and aj are similar, so our answer is 6.
  3. gig and aba are similar, so our answer is 2.
  4. igg has no similar string, so our answer is 1.
HackerRank Similar Strings Problem Solution
HackerRank Similar Strings Problem Solution

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()
c C# C++ HackerRank Solutions java javascript python

Leave a Reply