Click here to see the full article post
Maybe following sentence can be added in isSubsequence() function:
if(x.length()>y.length()) return false;
@donggua_fu you are right. You can add for optimization.
@vinod23. Can you explain this logic a bit " if (((i >> j) & 1) != 0) "
@priyeshnn-gmail.com Basically this condition checks the most significant bit(MSB) of i after shifting j bits right i.e. (i>>j). It will return true only if MSB of i>>j is equal to 1.
If n AND 1==0 then MSB of n is 0 else MSB is 1.
@vinod23. Thanks for your explanation .I was more curios about how you are deciding to sum up the individual characters to make the substring combination based on this check
@priyeshnn-gmail.com Consider the string "abc" of length 3. Total number of subsequences will be 2^3=8. We iterate i from 0 to 2^3-1=7 and check the three MSB's of i and consider the characters whose corresponding bits is 1.
0 - 000 - ""
1- 001 - "a"
2- 010 - "b"
3- 011 - "ab"
4- 100 - "c"
5- 101- "ac"
6- 110- "bc"
7- 111- "abc"
I don't quite understand this problem: if any string is a subsequence of itself, then a longest string couldn't be any subsequence of other strings because it is longer? Then it is the answer?
Can someone help me?
@Jerry consider the case ["de","abc","abc"]. Here longest string is of length 3 but output is 2.
For method 3, the sort algorithm costs O(n) space. Arrays.sort() for Object use Merge sort which costs O(n).
EDIT: After 2 hours i just realized that
Contiguous Subsequence is different than Subsequence that they are expecting here.
Read Question Properly. The above code will work for given case below.
The Second Solution will not work for your own testcase:
["aabbcc", "aabbcc", "cb", "abc"]
It will give output 3 while answer is 2
@vinod23 abc is itself common
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.