ASTRING - Editorial

I did it by greedy implementation with worst case complexity O(N*26).

Here is the link to my solution: CodeChef: Practical coding for everyone

I also first implemented using segment tree but got TLE. Then I finally got AC using sparse table with O(NlogN) space and O(1) per query.
Click here to see the solution

Even the O(N*K) algorithm with pruning worked for all test cases.
Code in C : CodeChef: Practical coding for everyone

1 Like

Can anyone explain what’s wrong with my code or any tricky test case?
my code

We can do it by using stack overall complexity O(n).My Solution link : CodeChef: Practical coding for everyone

2 Likes

“[…] The time complexity for the
above approach is O(N^2) but the space
complexity is around O(N^3). […]”

I do not understand this statement, how can the space complexity ever be bigger than the time complexity, how would you generate O(n) memory in O(1) time ?

https://www.codechef.com/viewsolution/10206440

Here is what I did. Just searched for the best possible element of the substring from left to right.

3 Likes

I too solved it using segment trees. First idea that came to my mind was using RMQ. Here’s my solution CodeChef: Practical coding for everyone

int main()
{char a[100005],b[100005];
int t,i,m;
scanf("%d",&t);
for(m=0;m<t;m++)
{int k,len;
scanf("%s",a);
scanf("%d",&k);
len=strlen(a);
int p=len-k;
int j=0;
for(i=0;i<len;i++)
{
while(j!=0 && b[j-1]>a[i] && p!=0)
{
j–;
p–;
}
b[j]=a[i];
j++;
}
b[k]=’\0’;
printf("%s\n",b);

}
return 0;
}

I just sorted the string and took the substring from 0 to k. But it shows wrong answer. Can someone please highlight the mistake in my code.

int main()
{

int t;
cin>>t;
while(t--)
{
    string s;
    cin>>s;
    int k;
    cin>>k;
    sort(s.begin(),s.end());
    string s1=s.substr(0,k);
    cout<<s1<<endl;

}

}

Yes, but that would be too much for this problem. :stuck_out_tongue:

1 Like

https://www.codechef.com/viewsolution/10208562

my this soln passed… i thought of using segment tree had it failed…

Since, you are storing a string at each dp[i][j], basically you are storing another array of characters in a 2D array. Hence, the space complexity is O(N^3).

complexity?

It is actually O( K*(N-K+1) ) which is approximately O(N)

no its not O(N)

Consider case when : K = N / 2
It goes O(N * N)

Sorry, that’s a typo…I meant to say O(N^2)

Same here - CodeChef: Practical coding for everyone

my solution is exact same as yours but that is giving only 30 points after submition. please check my solution.
https://www.codechef.com/viewsolution/10207113

1 Like

You have to update prev correctly. I have edited (only one small change) your code, check it here-

https://www.codechef.com/viewsolution/10252513