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):
#
# 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()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("%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
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;
}
0 Comments