You are not logged in. Please login at www.codechef.com to post your questions!

×

subanagr confusion

Please refer to this problem..

https://www.codechef.com/problems/SUBANAGR

I interpreted this question that we have to found the characters that are present in all the given set of strings... and display those in alpabetically sorted order..

Accordingly, I constructed solution like this:

include<iostream>

include<cstdio>

include<math.h>

include<algorithm>

include<string>

include<string.h>

include<ctype.h>

define mod 1000000007

define ll long long

define ull unsigned long long

using namespace std;

int main() {

int flag,k,j,t,i,min=200;
string s[110],o,ans;

scanf("%d",&t);

for(i=0;i<t;i++)
{
    cin>>s[i];
    if(s[i].length()<min)
    {
        min=s[i].length();
        k=i;
    }
}
    o=s[k];

    for(j=0;o[j];j++)
    {
        flag=0;
        for(i=0;i<t;i++)
        {
            if(s[i].find_first_of(o[j])>101)
            {
             flag=1;
             break;
            }

        }
            if(flag==0)
            ans=ans+o[j];
    }

    sort(ans.begin(),ans.end());
    if(ans.length()==0)
    cout<<"no such string";
    cout<<ans;






return 0;

}

Where am I wrong? It is working for the test cases I am able to think of?

asked 30 Nov '16, 20:27

pankajkhan's gravatar image

5★pankajkhan
1.2k10
accept rate: 15%


Your logic for the solution is correct, however there is a bug in your program. Consider the input
2 aa ab

Your code gives output "aa" whereas the correct answer is "a". If you dry run the program with this input, you'll find o = "aa", and consequently, searching through "ab" twice for the character 'a' finds the first 'a' both times. So your program believes wrongly that "ab" has 2 'a's.

A simple remedy to this is to set an already counted character to an non lowercase alphabet character so it does not get counted again. Consider replacing your inner loop with this

for(i=0; i<t; i++){
    k = s[i].find_first_of(o[j]);
    if(k==string::npos){
        flag=1;
        break;
    }
    else
        s[i][k] = '*'; //or any other non lowercase alphabet character
}

Although this is enough to get AC, this is quite an inefficient approach, $O(mn^2)$ to be precise where $m$ is the number of strings and $n$ is the maximum length of a string. An $O(mn)$ solution is possible if you make character frequency arrays out of the strings and use them instead. Take a look at this neat solution by udittidu. I hope this solves your problem!

link

answered 30 Nov '16, 22:46

meooow's gravatar image

6★meooow ♦
7.3k720
accept rate: 48%

edited 30 Nov '16, 23:12

I couldn't locate this bug yesterday while I was attempting this problem, but strangely when I woke up today, the first thoughts that were floating in my mind were regarding this problem. and the bug just striked me even when I wasn't not yet completely awake.. And, I corrected it to get AC.

Thanks for pointing to the better solution. And, thanks for giving time to the problem.

link

answered 01 Dec '16, 10:29

pankajkhan's gravatar image

5★pankajkhan
1.2k10
accept rate: 15%

@pankajkhan No problem, and I have experienced that too :)
Do accept the answer as correct, thanks!

(01 Dec '16, 15:15) meooow ♦6★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×354

question asked: 30 Nov '16, 20:27

question was seen: 407 times

last updated: 01 Dec '16, 15:15