HackerRank Square Subsequences Solution

Yashwant Parihar,

In this post, we will solve HackerRank Square Subsequences Problem Solution.

Square Subsequences

A string is called a square string if it can be obtained by concatenating two copies of the same string. For example, “abab”, “aa” are square strings, while “aaa”, “abba” are not. Given a string, how many (non-empty) subsequences of the string are square strings? A subsequence of a string can be obtained by deleting zero or more characters from it, and maintaining the relative order of the remaining characters.

Input Format

The first line contains the number of test cases, T.
 test cases follow. Each case contains a string, S.

Output Format

Output T lines, one for each test case, containing the required answer modulo 1000000007.

Sample Input

3
aaa
abab
baaba

Sample Output

3
3
6

Explanation

For the first case, there are 3 subsequences of length 2, all of which are square strings.
For the second case, the subsequences “abab”, “aa”, “bb” are square strings.
Similarly, for the third case, “bb”, “baba” (twice), and “aa” (3 of them) are the square subsequences.

HackerRank Square Subsequences Problem Solution
HackerRank Square Subsequences Problem Solution

Square Subsequences C Solution

#include <assert.h>
#include <limits.h>
#include <math.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MOD 1000000007

char* readline();

long commonSubsequences(char* a, char* b){
    int len1 = strlen(a);
    int len2 = strlen(b);
    long commonarray[len1 + 1][len2 + 1];
    for(int i = 0; i <= len1; i++){
        commonarray[i][len2] = 1;
    }
    for(int j = 0; j <= len2; j++){
        commonarray[len1][j] = 1;
    }
    for(int i = len1 - 1; i >= 0; i--){
        for(int j = len2 - 1; j >= 0; j--){
            commonarray[i][j] = (commonarray[i][j + 1] + commonarray[i + 1][j] + MOD - (a[i] == b[j]? 0 : commonarray[i + 1][j + 1]))%MOD;
        }
    }
    return commonarray[0][0] - 1;
}

int squareSubsequences(char* s) {
    long toreturn = 0;
    int len = strlen(s);
    for(int i = 0; i < len; i++){
        char* str1 = malloc(i + 1);
        strncpy(str1, s, i);
        str1[i] = '\0';
        char* str2 = malloc(len - i + 1);
        strncpy(str2, s + i, len - i);
        str2[len - i] = '\0';
        toreturn = (toreturn + commonSubsequences(str1, str2) + MOD - commonSubsequences(str1, str2 + 1))%MOD;
    }
    return toreturn;
}

int main()
{
    FILE* fptr = fopen(getenv("OUTPUT_PATH"), "w");

    char* t_endptr;
    char* t_str = readline();
    int t = strtol(t_str, &t_endptr, 10);

    if (t_endptr == t_str || *t_endptr != '\0') { exit(EXIT_FAILURE); }

    for (int t_itr = 0; t_itr < t; t_itr++) {
        char* s = readline();

        int result = squareSubsequences(s);

        fprintf(fptr, "%d\n", result);
    }

    fclose(fptr);

    return 0;
}

char* readline() {
    size_t alloc_length = 1024;
    size_t data_length = 0;
    char* data = malloc(alloc_length);

    while (true) {
        char* cursor = data + data_length;
        char* line = fgets(cursor, alloc_length - data_length, stdin);

        if (!line) { break; }

        data_length += strlen(cursor);

        if (data_length < alloc_length - 1 || data[data_length - 1] == '\n') { break; }

        size_t new_length = alloc_length << 1;
        data = realloc(data, new_length);

        if (!data) { break; }

        alloc_length = new_length;
    }

    if (data[data_length - 1] == '\n') {
        data[data_length - 1] = '\0';
    }

    data = realloc(data, data_length);

    return data;
}

Square Subsequences C++ Solution

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
#define maxn 210
const long long mod = 1000000007LL;
long long dp[maxn][maxn];
long long solve(const string &A, const string &B) {
  for (int i = 0; i < maxn; i ++) {
    for (int j = 0; j < maxn; j ++) dp[i][j] = 0;
  }
  for (size_t i = 0; i < B.size(); i ++) {
    if (A[0] == B[i]) {
      dp[0][i] = 1;
    }
    if (i) dp[0][i] += dp[0][i - 1];
    dp[0][i] %= mod;
  }
  for (size_t i = 1; i < A.size(); i ++) {
    dp[i][0] = dp[i - 1][0];
    for (size_t j = 1; j < B.size(); j ++) {
      dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1];
      if (A[i] == B[j]) dp[i][j] += dp[i - 1][j - 1];
      dp[i][j] %= mod;
    }
  }
  return dp[A.size() - 1][B.size() - 1];
}
int main() {
  int t;
  cin >> t;
  string T, A, B;
  while (t -- ) {
    cin >> T;
    long long ans = 0;
    for (size_t i = 1; i < T.size(); i ++) {
      ans += solve(T.substr(i, T.size() - i), T.substr(0, i));
      ans %= mod;
    }
    cout << ans << endl;
  }
  return 0;
}

Square Subsequences C Sharp Solution

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

class Solution {

    /*
     * Complete the squareSubsequences function below.
     */
    static int SquareSubsequences(string s)
    {
        const int Mod = 1000000007;

        // For the first j characters of s let count[e, s] equal the number of 
        // square subsequances where the first half end with e and the secind 
        // half starts with s. Given the next character c in s, c can extend 
        // count[e, s] if there exist i such that e < i < s and s[i] = c

        var count = new int[s.Length, s.Length];


        var prevousCharacters = new List<int>['z' - 'a' + 1];

        for (int i = 0; i < 'z' - 'a' + 1; i++)
        {
            prevousCharacters[i] = new List<int>();
        }

        for (int i = 0; i < s.Length; i++)
        {

            foreach (var occurance in 
                prevousCharacters[s[i] - 'a'].AsEnumerable().Reverse())
            {
                count[occurance, i] = 1;

                for (int end = 0; end < occurance; end++)
                {
                    for (int start = occurance + 1; start < i; start++)
                    {
                        count[occurance, start] = 
                            (count[occurance, start] + count[end, start]) % Mod;
                    }
                }
            }

            prevousCharacters[s[i] - 'a'].Add(i);
        }

        var result = 0;

        for (int i = 0; i < s.Length; i++)
        {
            for (int j = 0; j < s.Length; j++)
            {
                result = (result + count[i, j]) % Mod;
            }
        }

        return result;
    }

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

        int t = Convert.ToInt32(Console.ReadLine());

        for (int tItr = 0; tItr < t; tItr++) {
            string s = Console.ReadLine();

            int result = SquareSubsequences(s);

            textWriter.WriteLine(result);
        }

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

Square Subsequences Java Solution

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.regex.*;
import java.util.stream.*;
import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;

class Result {

    /*
     * Complete the 'squareSubsequences' function below.
     *
     * The function is expected to return an INTEGER.
     * The function accepts STRING s as parameter.
     */

    private static final long MODULUS = 1_000_000_007;
    
    private static long commonSubsequenceCount(String a, String b){
        char[] sa = a.toCharArray();
        char[] sb = b.toCharArray();
        int n = sa.length;
        int m = sb.length;
        if (n==0){return 0;}
        if (m==0){return 0;}
        long[][] c = new long[n][m];
        if (sa[0] == sb[0]){
            c[0][0] = 1; 
        } else {
            c[0][0] = 0;
        }
        for (int j=1; j<m; j++){
            if (sa[0] == sb[j]){
                // 1 + c{i, j-1}
                c[0][j] = 1 + c[0][j-1];
                c[0][j] %= MODULUS;
            } else {
                // c[i, j-1]
                c[0][j] = c[0][j-1];
            }
        }
        for (int i=1;i<n; i++){
            if (sa[i] == sb[0]){
                // 1 + c_{i-1, j}
                c[i][0] = 1 + c[i-1][0];
                c[i][0] %= MODULUS;
            } else {
                // c[i-1, j]
                c[i][0] = c[i-1][0];
            }
            for (int j=1; j<m; j++){
                if (sa[i] == sb[j]){
                    // 1 + c_{i-1, j} + c{i, j-1} - c[i-1, j-1] + c[i-1, j-1]
                    c[i][j] = 1 + c[i-1][j] + c[i][j-1];
                    c[i][j] %= MODULUS;
                } else {
                // c[i-1, j] + c[i, j-1] - c[i-1, j-1]
                    c[i][j] = c[i-1][j] + c[i][j-1] + MODULUS - c[i-1][j-1];
                    c[i][j] %= MODULUS;
                }
            }
        }
        return c[n-1][m-1];
    }
    
    public static int squareSubsequences(String s) {
        int n = s.length();
        char[] c = s.toCharArray();
        long count = 0;
        for (int i=0; i<n; i++){
            for (int j=0;j<i; j++){
                if (c[i]==c[j]){
                    count+= commonSubsequenceCount(s.substring(j+1, i), s.substring(i+1)) + 1;
                    count %= MODULUS;
                }
            }
        }
        return (int)count;
        // f_i: common subsequences s.t. first one ends at i at i. 0<=i<=n-1
        // f_i = g_{i,0}
        // g_{i, j}: common subsequences s.t. first one ends at i and first one may start at j
        // g_{i, j} = if s[i] = s[j] -> sum { h_{i+1..n-1, j+1..i-1} +1, 
        //                                    g_{i, j+1}}
        //               else        -->   g_{i, j+1}
    }

}

public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        int t = Integer.parseInt(bufferedReader.readLine().trim());

        IntStream.range(0, t).forEach(tItr -> {
            try {
                String s = bufferedReader.readLine();

                int result = Result.squareSubsequences(s);

                bufferedWriter.write(String.valueOf(result));
                bufferedWriter.newLine();
            } catch (IOException ex) {
                throw new RuntimeException(ex);
            }
        });

        bufferedReader.close();
        bufferedWriter.close();
    }
}

Square Subsequences JavaScript Solution

const maxn = 200;
const mod = 1000000007;

function countSquareSubseq(A, B) {
    let dp = new Array(maxn);
    for (let i = 0; i < maxn; i++) {
        dp[i] = new Array(maxn);
        for (let j = 0; j < maxn; j++) {
            dp[i][j] = 0;  
        }
    }
    for (let i = 0; i < B.length; i++) {
        if (A[0] == B[i]) {
            dp[0][i] = 1;
        }
        if (i) {
            dp[0][i] += dp[0][i-1];
        }
        dp[0][i] %= mod;
    }
    for (let i = 1; i < A.length; i++) {
        dp[i][0] = dp[i-1][0];
        for (let j = 1; j < B.length; j++) {
            dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1];
            if (A[i] == B[j]) {
                dp[i][j] += dp[i-1][j-1];
            }
            dp[i][j] %= mod;
        }
    }
    if (!dp[A.length-1]) {
        console.log("wut?",A.length - 1,dp[A.length - 1]);    
    }
    return dp[A.length-1][B.length-1];
}

function processData(input) {
    input = input.split('\n');
    input.shift();
    for (let v of input) {
        let ans = 0;
        for (let i = 1; i < v.length; i++) {
            ans += countSquareSubseq(v.substring(i, v.length), v.substring(0, i));
            ans %= mod;
        }
        console.log(ans);        
    }
} 

process.stdin.resume();
process.stdin.setEncoding("ascii");
_input = "";
process.stdin.on("data", function (input) {
    _input += input;
});

process.stdin.on("end", function () {
   processData(_input);
});

Square Subsequences Python Solution

NUMBER = 1000000007

def solve_sub(string, size):
    s1 = string[:size]
    size1 = len(s1) + 1
    s2 = string[size:]
    size2 = len(s2) + 1
    N = [[0 for j in range(size2)] for i in range(size1)]

    for i in range(1, size1):
        for j in range(1, size2):
            if s1[i - 1] == s2[j - 1]:
                N[i][j] = N[i - 1][j] + N[i][j - 1] + 1
            else:
                N[i][j] = N[i - 1][j] + N[i][j - 1] - N[i - 1][j - 1]

    return N[-1][-1] - N[-2][-1]

def solve(string):
    count = sum(solve_sub(string, i) for i in range(1, len(string)))
    return count % NUMBER

if __name__ == '__main__':
    import sys
    _ = sys.stdin.readline()
    for line in sys.stdin:
        print(solve(line.strip()))
c C# C++ HackerRank Solutions java javascript python