j
BAN USERYou can improve this solution. This solution is O(nm), n = lenght of src, m = length of target. We can do this in O(n) time.
In your code above, to check if a substring is an anagram takes O(m).
//check if substring is an anagram
for(j = 0; j < targetLen; ++j){
if(count[target[j]] != targetCount[target[j]]) break;
}
You may do this in O(1) time. Maintain an int variable matchedCount that counts the number of matched characters in current substring(window) and target.
Store target chars in a HashSet to be able to use set.contains() which is O(1).
As you slide the window 1 step to the right, check the following:
1. Decrement matchedCount if the dropped character from the prev window is in target string (use the hashset to query) and if the count of that character after dropping it is now less than its target count.
2.Increment matchedCount if the new character in the new window is in target string (hashset) and if count of that character was less than the targetCount before it was added.
For each iteration (each window), check if matchedCount == target.length() and return true if it is.
Overall time complexity is n * O(1) = O(n)
Array.sort is O(nLogN). To keep the total time complexity linear, just reverse the remaining digits as they are already sorted in descending manner from left to right.
- j May 16, 2014