HackerRank Square Subsequences problem solution

In this HackerRank Square Subsequences problem solution 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.

HackerRank Square Subsequences problem solution in Python.

#!/bin/python3

import os
import sys
from collections import Counter

def solveSub(s,size):
    s1 = s[:size]
    s1Len = len(s1)+1
    s2 = s[size:]
    s2Len = len(s2)+1
    sMatrix = [[0 for j in range(s2Len)] for i in range(s1Len)]
    for i in range(1,s1Len):
        for j in range(1,s2Len):
            if s1[i-1]==s2[j-1]:
                sMatrix[i][j]=sMatrix[i-1][j]+sMatrix[i][j-1]+1
            else:
                sMatrix[i][j]=sMatrix[i-1][j]+sMatrix[i][j-1]-sMatrix[i-1][j-1]
    return sMatrix[-1][-1]-sMatrix[-2][-1]


#
# Complete the squareSubsequences function below.
#
def squareSubsequences(s):
    #
    # Write your code here.
    #
    count = sum(solveSub(s,i) for i in range(1,len(s)))
    return count%1000000007
    


if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    t = int(input())

    for t_itr in range(t):
        s = input()

        result = squareSubsequences(s)

        fptr.write(str(result) + 'n')

    fptr.close()

Square Subsequences problem solution in Java.

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

public class Solution implements Runnable {
    final static int MOD = 1000000007;

    int count(String a, String b) {
        int n = a.length();
        int m = b.length();
        int dp[][] = new int[n + 1][m + 1];
        int sum[][] = new int[n + 1][m + 1];
        for (int i = 0; i <= n; ++ i) {
            sum[i][m] = 1;
        }
        for (int j = 0; j <= m; ++ j) {
            sum[n][j] = 1;
        }
        for (int i = n - 1; i >= 0; -- i) {
            for (int j = m - 1; j >= 0; -- j) {
                if (a.charAt(i) == b.charAt(j)) {
                    dp[i][j] = sum[i + 1][j + 1];
                } 
                sum[i][j] = (sum[i + 1][j] + sum[i][j + 1]
                    - sum[i + 1][j + 1] + dp[i][j]) % MOD;
            }
        }
        int result = 0;
        for (int i = 0; i < n; ++ i) {
            result += dp[i][0];
            result %= MOD;
        }
        return result;
    }

    int count(String s) {
        int n = s.length();
        int result = 0;
        for (int i = 1; i < n; ++ i) {
            result += count(s.substring(0, i), s.substring(i, n));
            result %= MOD;
        }
        return (result + MOD) % MOD;
    }

    public void run() {
        try {
            BufferedReader reader = new BufferedReader(
                    new InputStreamReader(System.in));
            int testCount = Integer.parseInt(reader.readLine());
            while (testCount > 0) {
                testCount --;
                System.out.println(count(reader.readLine()));
            }
        } catch (Exception e) {
        }
    }

    public static void main(String args[]) {
        new Thread(new Solution()).run();
    }
}

Problem solution in C++.

/* Enter your code here. Read input from STDIN. Print output to STDOUT */
#include <cstdio>
#include <cstring>

static inline long long
getone(char *s, int ns, char *t, int nt, int last)
{
	if (ns <= 0 or nt <= 0)
		return 1; // empty string
	static long long count[204][204];
	for (int i = 0; i < ns; i++)
		for (int j = last; j < nt; j++) {
			long long &now = count[i][j];
			now = 0;
			long long a = 1;
			if (j >= 1)
				a = count[i][j-1];
			long long b = 1;
			if (i >= 1)
				b = count[i-1][j];
			long long c = 1;
			if (i >=1 and j >= 1)
				c = count[i-1][j-1];
			now += a + b - c;
			if (s[i] == t[j])
				now += c;
			now %= 1000000007;
		}
	return count[ns-1][nt-1];
}

static long long
get(char *s)
{
	int n = strlen(s);
	long long ret = 0;
	for (int i = 0; i < n; i++) {
		char c = s[i];
		int last = 0;
		for (int j = i + 1; j < n; j++)
			if (s[j] == c) {
				ret += getone(s, i, s+i+1, j-i-1, last);
				ret %= 1000000007;
				if (j-i-1 > 0)
					last = j-i-1;
			}
	}
	return (ret + 1000000007) % 1000000007;
}

int
main()
{
	int t;
	scanf("%d", &t);
	while (t--) {
		char s[204];
		scanf("%s", s);
		printf("%lldn", get(s));
	}
	return 0;
}

Problem solution in C.

#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] = '';
        char* str2 = malloc(len - i + 1);
        strncpy(str2, s + i, len - i);
        str2[len - i] = '';
        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 != '') { exit(EXIT_FAILURE); }

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

        int result = squareSubsequences(s);

        fprintf(fptr, "%dn", 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] = '';
    }

    data = realloc(data, data_length);

    return data;
}