-VIBE's blog

Stuck on a problem
By -VIBE, history, 21 month(s) ago, In English

Can anyone help me with my last submission. Approach-> 1)Lets take any two strings(say s1 and s2). 2)Now create a string ans from s1 and s2 by taking first character from s1 and then s2 and then repeat. At last we have size of our string ans=4*n. 3)Now i will pair the consecutive same number in the ans string. 4)Now if size of ans is less than or equal to 3*n then it will be my ans otherwise i will create my ans string from s2 and s3,then check for it and lastly check for s1 and s3. Note-> A number can only be paired once. Thanks in advance

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

provide question link

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Actually, you are pairing them wrong.

Let's take these two strings:

000111

111000

(here n=3)

By your algorithm, the merged string comes out to be '010101101010' and then you merge '11'. The string becomes '01010101010'. The length is 11 which is greater than 3*n=9, so you say that this merging is not possible and move forwards to compare s2 and s3.

Whereas, the string '000111000' has length 9 and contains both strings as it's subsequence.

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Ya i got the mistake , but could there be any third string along with these two such that ans will not exist for three of them. Coz i guess my ans will come for the third string

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Below is an counter-example with all 3 strings. All the 6 merging results exceeds maximal length 12: 11111000 00000000 00101111

        11111000 00000000 -> 1010101010000
  11111000 00101111 -> 10101101010101
  00000000 11111000 -> 0101010101000
  00000000 00101111 -> 0001001010101
  00101111 11111000 -> 0101101101010
  00101111 00000000 -> 0010010101010
      → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        thanks....will try another approach

        → Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

my stepsister is stuck in the washing machine too

→ Reply