How is the space complexity O(1),when you are using extra space in the form of dictionary and also the size of the dictionary is not constant and will depend on the length of the user input string.I have a confusion regarding this, explain please.
This is because the maximum possible size of the dictionary is constant right , we have finite number of characters right (max 256 ASCII) so technically the worst case space complexity is O(256) which can be considered as constant space.
Sorting them takes O(n logn) complexity and comparing them takes O(n) complexity ,,,,,, creating a dictionary gives O(n) complexity and space can be considered as constant . Overall this looked a better approach for me 🙂.
i have checked it through sorted function but it showing time limit exceeded. why time limit is exceeding? if len(a)!=len(b): return -1 sorted_a = sorted(a) sorted_b = sorted(b) if sorted_a != sorted_b: return -1
ans=0 n = len(a) i=j=n-1 while(i>=0): while(i>=0 and a[i]!=b[j]): ans+=1 i-=1 if(i>=0): i-=1 j-=1 return ans
Abort signal from abort(3) (SIGABRT) this is the error for some testcases.. do you know what might be wrong ans=0; i=j=a-1; for (i=a-1, j=a-1; i>=0; ) { while(i>=0 && A[i]!=B[j]) {i--; ans++; } if(i>=0) {i--;j--;} } return ans++; gives correct out put for sample testcases
Congo and all the beat 🎉
All the best in GFG!
Please mention the channel name where your further videos would be posted
Remaining Videos of the 30Daycodingchallenge playlist will be posted on official RUclips channel of Geeksforgeeks starting Tomorrow .
How is the space complexity O(1),when you are using extra space in the form of dictionary and also the size of the dictionary is not constant and will depend on the length of the user input string.I have a confusion regarding this, explain please.
This is because the maximum possible size of the dictionary is constant right , we have finite number of characters right (max 256 ASCII) so technically the worst case space complexity is O(256) which can be considered as constant space.
You can have a string of infinite length ..... But the dictionary size is 256 only ... Hope you understood .
This was a wonderful doubt 🙂🤝
Got it now!Thanks a lot for the explanation.Keep up the good work and all the best!
Wow. All the best bro! See you in gfg
can we simply sort the strings and compare with each other instead of creating dictonary and doing all that stuff.
Sorting them takes O(n logn) complexity and comparing them takes O(n) complexity ,,,,,,
creating a dictionary gives O(n) complexity and space can be considered as constant .
Overall this looked a better approach for me 🙂.
i have checked it through sorted function but it showing time limit exceeded.
why time limit is exceeding?
if len(a)!=len(b):
return -1
sorted_a = sorted(a)
sorted_b = sorted(b)
if sorted_a != sorted_b:
return -1
ans=0
n = len(a)
i=j=n-1
while(i>=0):
while(i>=0 and a[i]!=b[j]):
ans+=1
i-=1
if(i>=0):
i-=1
j-=1
return ans
Check the above comment ... Sorting is costlier in terms of time complexity .
Abort signal from abort(3) (SIGABRT) this is the error for some testcases.. do you know what might be wrong
ans=0;
i=j=a-1;
for (i=a-1, j=a-1; i>=0; )
{
while(i>=0 && A[i]!=B[j])
{i--;
ans++;
}
if(i>=0)
{i--;j--;}
}
return ans++;
gives correct out put for sample testcases
Not sure about the error ... but try to return ans instead of ans++
Bhai plz speak hindi, I saw yr video 3 times but unable to understand
hey Arshad,
Hindi is not my mother tongue and So I don't think I can 😅
@@SaiprakashReddy oh sorry