### R.A.N.K.A.'s blog

By R.A.N.K.A., history, 2 years ago,

Jamie is walking along a number line that starts at point 0 and ends at point n. She can move either one step to the left or one step to the right of her current location , with the exception that she cannot move left from point 0 or right from point n. In other words, if Jamie is standing at point i,she can move to either i-1 or i+1 as long as her destination exists in the inclusive range [0,n]. She has a string ,s , of movement instruction consisting of the letters 1 and r , where 1 is an instruction to move one step left and r is an instruction to move one step right. Jamie followed the instructions in s one by one and in order .For Example if s=‘rrlr’,she performs the following sequence of moves :one step right ->one step right ->one step left -> one step right .Jamie wants to move from point x to point y following some subsequence of string s instruction and wonders how many distinct possible subsequence of string s will get her from point x to point y. recall that a subsequence of a string is obtained by deleting zero or more characters from string .

it has four parameters A String , s giving a sequence of eduction using the characters l( i.e. move left one unit ) and r (i.e. move right one unit) An integer n, denoting the length of the number line. An integer x, denoting jamie’s starting point on the number line An integer y , denoting Jamie’s enidng point on the number line. The function must return an integer denoting the total number of distinct subsequence of string s that will lead Jamie from point x to point y as this value cab be quite large .

Sample Input rrlrlr 6 1 2

out put =7

r
rrl
rlr
lrr
rrlrl
rlrlr
rrllr



• +8

By R.A.N.K.A., history, 2 years ago,

Problem statement — Permutation is called stable if P[i]=i for every i

We are given Permutation we want to tell in how many moves we can make this permutation stable or print -1 if not possible to make permutation stable.

in one move we can do operation : — P[i] = P[P[i]]

Sample TestCase
7
[1 3 2 5 6 7 4]
Output  - > 2

[1 3 2 5 6 7 4] -> [1 2 3 6 7 4 5] -> [1 2 3 4 5 6 7]

Sample TestCase
7
[2 3 1 5 6 7 4]
Output  - > -1



• +6

By R.A.N.K.A., history, 2 years ago,

In this problem,Nodes with duplicate values are not present.

class Solution {
public boolean flipEquiv(TreeNode root1, TreeNode root2) {
if (root1 == root2)
return true;
if (root1 == null || root2 == null || root1.val != root2.val)
return false;

return (flipEquiv(root1.left, root2.left) && flipEquiv(root1.right, root2.right) ||
flipEquiv(root1.left, root2.right) && flipEquiv(root1.right, root2.left));
}
}


What would be the time complexity of this code if node with duplicate values were also present??

How Can I improve my code so that it also works with duplicate values?

• +9

By R.A.N.K.A., history, 3 years ago,

I am not able to point out my mistake in this code Can someone help me out to debug my code

Submission

I tried to solve this problem using centroid decomposition methed explained in this editorail :- editoial

• +3

By R.A.N.K.A., history, 3 years ago,

Can anyone help me out.

why this code is giving time limit error(tle):

int fun(vector<vector<int> > &dp,int i,int j,string s1,string s2)
{
if(i==s1.length()|| j==s2.length()) return 0;
int &ans=dp[i][j];
if(ans!=-1) return ans;
ans=max(fun(dp,i,j+1,s1,s2),fun(dp,i+1,j,s1,s2));
if(s1[i]==s2[j])
ans=max(ans,1+fun(dp,i+1,j+1,s1,s2));
return ans;
}

int Solution::solve(string s1, string s2) {
if(!s1.length() || !s2.length())    return 0;
int n=s1.size(),m=s2.size();
vector<vector<int> > dp(n,vector<int> (m,-1));
return fun(dp,0,0,s1,s2);
}


and why this code get accepted:

×

int Solution::solve(string s1, string s2) {
if(!s1.length() || !s2.length())    return 0;
int n=s1.size(),m=s2.size(),i,j;
vector<vector<int> > dp(n+1,vector<int> (m+1,0));
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
{
if(s1[i-1]==s2[j-1])
dp[i][j]=1+dp[i-1][j-1];
else
dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
}
return dp[n][m];
}


both solutions have time complexity O(m*n) memoization gives tle and tabulation passes the constraints why?? Thanks in advance.

• -10