Square Subsequences – HackerRank Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.
Solutions of Algorithms Data Structures Hard HackerRank:
Here are all the Solutions of Hard , Advanced , Expert Algorithms of Data Structure of Hacker Rank , Leave a comment for similar posts
C++ Square Subsequences HackerRank Solution
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
#include<iostream>
#include<set>
#include<map>
#include<string>
#include<stdio.h>
#include<sstream>
#include<algorithm>
#include<queue>
#include<cmath>
#include<string.h>
using namespace std ;
#define MAXN 305
#define INF (int)1e9
#define MOD 1000000007
int brute(string s)
{
int n = s.size() ;
int ret = 0 ;
for(int i = 1;i < 1 << n;i++)
{
string t ;
for(int j = 0;j < n;j++)
if(i & 1 << j)
t.push_back(s[j]) ;
if(t.size() % 2 == 1) continue ;
int tt = t.size() ;
bool valid = true ;
for(int j = 0;j < tt / 2;j++)
if(t[j] != t[tt / 2 + j])
valid = false ;
if(valid) ret++ ;
}
return ret ;
}
string s ;
int n ;
int start1,start2 ;
int memo[MAXN][MAXN] ;
int solve(int k1,int k2)
{
if(k1 == start2 || k2 == n) return 0 ;
int ret = s[k1] == s[k2] ? 1 : 0 ;
if(memo[k1][k2] != -1) return memo[k1][k2] ;
ret += solve(k1 + 1,k2) ;
ret += solve(k1,k2 + 1) ;
if(ret >= MOD) ret -= MOD ;
ret -= solve(k1 + 1,k2 + 1) ;
if(ret < 0) ret += MOD ;
if(s[k1] == s[k2]) ret += solve(k1 + 1,k2 + 1) ;
if(ret >= MOD) ret -= MOD ;
return memo[k1][k2] = ret ;
}
int solve(string _s)
{
s = _s ;
n = s.size() ;
int ret = 0 ;
for(start2 = 0;start2 < n;start2++)
{
memset(memo,255,sizeof memo) ;
for(start1 = 0;start1 < start2;start1++)
if(s[start1] == s[start2])
{
int cret = 1 + solve(start1 + 1,start2 + 1) ;
ret += cret ;
if(ret >= MOD) ret -= MOD ;
}
}
return ret ;
}
void test()
{
for(int test = 0;test < 10000;test++)
{
int n = rand() % 10 + 1 ;
string t ;
for(int j = 0;j < n;j++) t.push_back('a' + rand() % 2) ;
int ret1 = brute(t) ;
int ret2 = solve(t) ;
cout << ret1 << " " << ret2 << endl ;
if(ret1 != ret2)
{
cout << "Failed on: " << test << endl ;
cout << t << endl ;
while(1) ;
}
}
}
void generate()
{
char in[10] = "in .txt" ;
for(int test = 0;test < 10;test++)
{
in[2] = test + '0' ;
FILE * fout = fopen(in,"w") ;
int runs = 20 ;
fprintf(fout,"%d\n",runs) ;
for(int t = 0;t < runs;t++)
{
string c ;
int n = rand() % 200 + 1 ;
if(test < 2) n = rand() % 20 + 1 ;
if(test < 4) for(int i = 0;i < n;i++) c.push_back(rand() % 26 + 'a') ;
else if(test < 7) for(int i = 0;i < n;i++) c.push_back(rand() % 3 + 'a') ;
else if(test < 10) for(int i = 0;i < n;i++) c.push_back(rand() % 2 + 'a') ;
fprintf(fout,"%s\n",c.c_str()) ;
}
}
}
int main()
{
// test() ; return 0 ;
// generate() ; return 0 ;
int runs ;
cin >> runs ;
while(runs--)
{
string s ;
cin >> s ;
int ret = solve(s) ;
cout << ret << endl ;
}
return 0 ;
}
Java rep HackerRank Solution
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();
}
}
Python 3 Square Subsequences HackerRank Solution
def count_square_subsequences(s, t):
m = len(s)
n = len(t)
T = [[0 for _ in range(n)] for _ in range(m)]
T[0][0] = 1 if s[0] == t[0] else 0
for i in range(1, n):
T[0][i] = T[0][i - 1] + (1 if s[0] == t[i] else 0)
T[0][i] %= 1000000007
for i in range(1, m):
T[i][0] = T[i - 1][0]
T[i][0] %= 1000000007
for i in range(1, m):
for j in range(1, n):
T[i][j] = T[i - 1][j] + T[i][j - 1] + (0 if s[i] == t[j] else -T[i - 1][j - 1])
T[i][j] %= 1000000007
return T[m - 1][n - 1]
def square_subsequences(string):
m = len(string)
R = 0
for i in range(1, m):
R += count_square_subsequences(string[i:], string[:i])
R %= 1000000007
return R
def main():
T = int(input())
for _ in range(T):
print(square_subsequences(input()))
if __name__ == "__main__":
main()
Python 2 Square Subsequences HackerRank Solution
import sys
import array;
def CountCommonSequence(s1, s2):
size1 = len(s1)
size2 = len(s2)
css = [x[:] for x in [[0]*size2]*size1]
for i in range(1,size1):
for j in range(1,size2):
css[i][j] = 0
k = 0
for i in range(0,size1):
if(s1[i] == s2[0]):
k = k + 1
css[i][0] = k
k = 0
for j in range(0,size2):
if(s1[0] == s2[j]):
k = k + 1
css[0][j] = k
i = 1;
j = 1;
while i < size1 and j < size2:
for x in range(i,size1):
css[x][j] = css[x-1][j] + css[x][j-1] - css[x-1][j-1]
if(s1[x] == s2[j]): css[x][j] = css[x][j] + css[x-1][j-1] + 1
for y in range(j,size2):
css[i][y] = css[i-1][y] + css[i][y-1] - css[i-1][y-1]
if(s1[i] == s2[y]): css[i][y] = css[i][y] + css[i-1][y-1] + 1
i = i + 1
j = j + 1
'''
print("===========")
for i in range(0,size1):
print(css[i])
pass;
'''
ret = css[size1-1][size2-1]
if(size1 - 1 > 0):
ret = ret - css[size1-2][size2-1]
return ret
def CountSquares(strin):
count = 0
if len(strin) <= 1:
return 0
for i in range(1,len(strin)):
strl = strin[0 : i]
strr = strin[i:]
more = CountCommonSequence(strl, strr);
count = count + more;
#print("%s : %s + %s" % (strl,strr,more))
return count
data = sys.stdin.readlines()
#CountCommonSequence("jmowf", "rxsjybldbef");
lines = int(data[0])
count = 0;
for strin in data[1:]:
print(CountSquares(strin) % 1000000007)
count = count + 1
if(count == lines): break;
#print(strin + " has " +str(CountSquares(strin)) + " squares")
C Square Subsequences HackerRank Solution
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
#include <stdio.h>
#define MAX_BUF_SIZE 500
#define CHAR_SET_SIZE 256
char gBuffer[MAX_BUF_SIZE+1];
long m[MAX_BUF_SIZE][MAX_BUF_SIZE];
int indexes[CHAR_SET_SIZE][MAX_BUF_SIZE];
long Module = 1000000007;
char* ReadLine(){
scanf("%s", gBuffer);
return gBuffer;
}
int GetTestCaseNumber(){
return atoi(ReadLine());
}
int Max(int a, int b){
return a > b ? a : b;
}
void BuildMatrix(char *line, int startA,int endA, int startB, int endB){
int aIndex, bIndex;
int aLength = endA - startA +1;
int bLength = endB - startB + 1;
long curValue;
int i,len;
char ch;
if (aLength <= 0 || bLength <= 0) return ;
for (bIndex = 0 ; bIndex <= bLength; bIndex++) m[0][bIndex] = 0;
for (aIndex = 1; aIndex <= aLength; aIndex++){
m[aIndex][0] = 0;
for (bIndex = 1; bIndex <= bLength; bIndex++){
curValue = m[aIndex][bIndex-1];
ch = line[startB + bIndex - 1];
len = indexes[ch][0];
i = 1;
while (i <= len){
if (indexes[ch][i] > startA + aIndex -1) {
break;
}
curValue = (curValue + m[indexes[ch][i]-startA][bIndex-1] +1)% Module;
i++;
}
m[aIndex][bIndex] = curValue;
}
}
//printf("m = %u aLength = %d bLength=%d\n", m[bLength][aLength], aLength, bLength);
// return m[bLength][aLength];
return;
}
void BuildIndex(char* line){
int i;
for (i = 0; i< CHAR_SET_SIZE ; i++) indexes[i][0] = 0;
i = 0;
while(line[i]){
indexes[line[i]][0] += 1;
indexes[line[i]][indexes[line[i]][0]] = i;
i++;
}
}
long GetSquareStringNumber(char *line){
int i = 0;
long count = 0;
int j;
int len = strlen(line);
char ch;
BuildIndex(line);
i = 0;
while (line[i]){
BuildMatrix(line, 0, i-1, i+1, len-1);
ch = line[i];
j = indexes[ch][0];
while (j > 0){
if (indexes[ch][j] <= i) break;
count = (count + m[i][indexes[ch][j] -i -1] + 1) % Module;
j--;
}
i++;
}
return count;
}
int main(int argc, char ** argv){
int testCaseNumber = GetTestCaseNumber();
int i;
long long n;
for (i = 0; i < testCaseNumber; i++){
n = GetSquareStringNumber(ReadLine());
printf("%d\n", (n%Module));
//printf("o = %u m = %u \n", n, n% 1000000007);
}
}
Warmup
Implementation
Strings
Sorting
Search
Graph Theory
Greedy
Dynamic Programming
Constructive Algorithms
Bit Manipulation
Recursion
Game Theory
NP Complete
Debugging
Leave a comment below