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 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
We can do it by using stack overall complexity O(n).My Solution link : CodeChef: Practical coding for everyone
“[…] 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.
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.
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)
You have to update prev correctly. I have edited (only one small change) your code, check it here-