Square Subsequence

Go To StackoverFlow.com

13

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 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.The subsequence need not be unique.

eg string 'aaa' will have 3 square subsequences

2012-04-03 19:44
by Avinash
What's your question? Other than, "please do my homework for me" - Greg Hewgill 2012-04-03 19:46
If this is a homework question, please label it as homework and say what you've done so far to approach the problem. (If this is not a homework question, I apologize.) Thanks - ninjagecko 2012-04-03 19:47
I came across this question in one of those programming challenges...i found it interesting but was unable to solve it. - Avinash 2012-04-03 20:16
This problem was originally stated on interviewstreet.com with more example - Colonel Panic 2012-07-02 10:45
Importantly, the original challenge asks for an efficient solution 'the string S may have as many as 200 characters - Colonel Panic 2012-07-02 10:53


8

Observation 1: The length of a square string is always even.

Observation 2: Every square subsequence of length 2n (n>1) is a combination of two shorter subsequences: one of length 2(n-1) and one of length 2.

First, find the subsequences of length two, i.e. the characters that occur twice or more in the string. We'll call these pairs. For each subsequence of length 2 (1 pair), remember the position of the first and last character in the sequence.

Now, suppose we have all subsequences of length 2(n-1), and we know for each where in the string the first and second part begins and ends. We can find sequences of length 2n by using observation 2:

Go through all the subsequences of length 2(n-1), and find all pairs where the first item in the pair lies between the last position of the first part and the first position of the second part, and the second item lies after the last position of the second part. Every time such a pair is found, combine it with the current subsequence of length 2(n-2) into a new subsequence of length 2n.

Repeat the last step until no more new square subsequences are found.

2012-04-05 21:59
by Jeffrey Sax
It seems like your method might work...the second observation really seems to simplyfy the problem...thanks a lot ma - Avinash 2012-04-06 18:40
For others' information, this technique - where you solve a problem by combining solutions to smaller cases of the same problem - is called dynamic programming. It's like recursion run in reverse - Colonel Panic 2012-07-04 19:22
Sorry..Could you please explain "for each subsequence of length 1"? Is that each char in the string? Thx - louis.luo 2012-08-06 00:15
Seems you have updated "of length 1" to "of length 2(1 pair)". Thanks - louis.luo 2012-08-15 06:09
Could you elaborate more regarding observation 2? I'm finding it hard to understand what your intention is in here - TheEmeritus 2015-12-20 18:18
This approach works, but my Python implementation times out on some of the test cases at https://www.hackerrank.com/challenges/square-subsequences - gsganden 2016-07-10 02:08


2

Psuedocode:

total_square_substrings <- 0

# Find every substring
for i in 1:length_of_string {

    # Odd strings are not square, continue
    if((length_of_string-i) % 2 == 1)
        continue;

    for j in 1:length_of_string {
        # Remove i characters from the string, starting at character j
        substring <- substr(string,0,j) + substr(string,j+1,length_of_string);

        # Test all ways of splitting the substring into even, whole parts (e.g. if string is of length 15, this splits by 3 and 5)
        SubstringTest: for(k in 2:(length_of_substring/2))
        {           
            if(length_of_substring % k > 0)
                continue;

            first_partition <- substring[1:partition_size];

            # Test every partition against the first for equality, if all pass, we have a square substring
            for(m in 2:k)
            {           
                if(first_partition != substring[(k-1)*partition_size:k*partition_size])
                    continue SubstringTest;
            }

            # We have a square substring, move on to next substring
            total_square_substrings++;
            break SubstringTest;
        }
    }
}
2012-04-05 20:11
by Ina
A subsequence need to be continuous. 'abacb' contains the square subsequence 'abab'. Your algorithm would miss that - Jeffrey Sax 2012-04-05 23:28
we are looking for square sunsequence....your algorithm seems to be searching for substrings and why did you assume a substring can have only one square subsequenc - Avinash 2012-04-06 18:56


0

Here's a solution using LINQ:

IEnumerable<string> input = new[] {"a","a","a"};

// The next line assumes the existence of a "PowerSet" method for IEnumerable<T>.
// I'll provide my implementation of the method later.
IEnumerable<IEnumerable<string>> powerSet = input.PowerSet();

// Once you have the power set of all subsequences, select only those that are "square".
IEnumerable<IEnumerable<string>> squares = powerSet.Where(x => x.Take(x.Count()/2).SequenceEqual(x.Skip(x.Count()/2)));

Console.WriteLine(squares);

And here is my PowerSet extension method, along with a "Choose" extension method that is required by PowerSet:

public static class CombinatorialExtensionMethods
{
    public static IEnumerable<IEnumerable<T>> Choose<T>(this IEnumerable<T> seq, int k)
    {
        // Use "Select With Index" to create IEnumerable<anonymous type containing sequence values with indexes>
        var indexedSeq = seq.Select((Value, Index) => new {Value, Index});

        // Create k copies of the sequence to join
        var sequences = Enumerable.Repeat(indexedSeq,k);

        // Create IEnumerable<TypeOf(indexedSeq)> containing one empty sequence
        /// To create an empty sequence of the same anonymous type as indexedSeq, allow the compiler to infer the type from a query expression
        var emptySequence =
            from item in indexedSeq
            where false
            select item;
        var emptyProduct = Enumerable.Repeat(emptySequence,1);

        // Select "Choose" permutations, using Index to order the items
        var indexChoose = sequences.Aggregate( 
            emptyProduct,
            (accumulator, sequence) =>  
            from accseq in accumulator  
            from item in sequence
            where accseq.All(accitem => accitem.Index < item.Index)
            select accseq.Concat(new[] { item }));

        // Select just the Value from each permutation
        IEnumerable<IEnumerable<T>> result = 
            from item in indexChoose
            select item.Select((x) => x.Value);

        return result;
    }

    public static IEnumerable<IEnumerable<T>> PowerSet<T>(this IEnumerable<T> seq)
    {
        IEnumerable<IEnumerable<T>> result = new[] { Enumerable.Empty<T>() };
        for (int i=1; i<=seq.Count(); i++)
        {
            result = result.Concat(seq.Choose<T>(i));
        }
        return result;
    }
}
2012-04-05 20:42
by mbeckish


0

I initially derive all possible sub-sequences and then i will check if the derived sub-sequence is a square sub-sequence or not

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

  public class Subsequence { 
  static int count;
  public static void print(String prefix, String remaining, int k) {

    if (k == 0) {
        //System.out.println(prefix);
        if(prefix.length() %2 == 0 && check(prefix) != 0 && prefix.length() != 0)
        {
            count++;
            //System.out.println(prefix);
        }
        return;
    }
    if (remaining.length() == 0) 
        return;

    print(prefix + remaining.charAt(0), remaining.substring(1), k-1);
    print(prefix, remaining.substring(1), k);
 }


 public static void main(String[] args) 
 {
    //String s = "aaa";
    Scanner sc = new Scanner(System.in);
    int t=Integer.parseInt(sc.nextLine());
    while((t--)>0)
    {
        count = 0;
        String s = sc.nextLine();
        for(int i=0;i<=s.length();i++)
        {
             print("",s,i);
        }
        System.out.println(count);
     }
 }

 public static int check(String s)
 {
    int i=0,j=(s.length())/2;

    for(;i<(s.length())/2 && j < (s.length());i++,j++)
    {
        if(s.charAt(i)==s.charAt(j))
        {
                continue;
        }

        else
           return 0;
    }

    return 1;
}

}
2015-05-13 12:35
by coder101
Please give an estimate of the space required - greybeard 2015-05-13 12:40
It takes way too much space if the string is very long , i am actually trying to find a better solution , still working on i - coder101 2015-05-13 12:42


0

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

public class Solution {
    /*
        Sample Input:
        3 
        aaa 
        abab 
        baaba

        Sample Output:
        3 
        3 
        6
    */
    public static void main(String[] args) {
        //Creating an object of SquareString class
        SquareString squareStringObject=new SquareString();
        Scanner in = new Scanner(System.in);
        //Number of Test Cases
        int T = in.nextInt();
        in.nextLine();
        String[] inputString=new String[T];
        for(int i=0;i<T;i++){
            // Taking input and storing in String Array
            inputString[i]=in.nextLine();
        }
        for(int i=0;i<T;i++){
            //Calculating and printing the number of Square Strings
            squareStringObject.numberOfSquareStrings(inputString[i]);
        }
    }
}
class SquareString{
    //The counter maintained for keeping a count of Square Strings
    private int squareStringCounter;
    //Default Constructor initialising the counter as 0
    public SquareString(){
        squareStringCounter=0;
    }
    //Function calculates and prints the number of square strings
    public void numberOfSquareStrings(String inputString){
        squareStringCounter=0;
        //Initialising the string part1 as a single character iterated over the length
        for(int iterStr1=0;iterStr1<inputString.length()-1;iterStr1++){
            String str1=""+inputString.charAt(iterStr1);
            String str2=inputString.substring(iterStr1+1);
            //Calling a recursive method to generate substring
            generateSubstringAndCountSquareStrings(str1,str2);
        }
        System.out.println(squareStringCounter);
    }
    //Recursive method to generate sub strings
    private void generateSubstringAndCountSquareStrings(String str1,String str2){
        for(int iterStr2=0;iterStr2<str2.length();iterStr2++){
            String newStr1=str1+str2.charAt(iterStr2);
            if(isSquareString(newStr1)){
                squareStringCounter++;
            }
            String newStr2=str2.substring(iterStr2+1);
            generateSubstringAndCountSquareStrings(newStr1,newStr2);
        }
    }
    private boolean isSquareString(String str){
        if(str.length()%2!=0)
            return false;
        String strPart1=str.substring(0,str.length()/2);
        String strPart2=str.substring(str.length()/2);
        return strPart1.equals(strPart2);
    }
}
2017-06-09 06:13
by Biplob Manna