# 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.

## 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):
#
#
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()```

## 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 {
while (testCount > 0) {
testCount --;
}
} catch (Exception e) {
}
}

public static void main(String args[]) {
}
}
```

## 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("%lld\n", 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

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;
}
}

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

char* t_endptr;
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++) {

int result = squareSubsequences(s);

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

fclose(fptr);

return 0;
}

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;
}```