sakar2003
BAN USERIt's easy to get a O(n) solution. We only need to find the length of first k characters that it's already satisfy palindrome.
Just think about KMP.
Here is the solution:
1. String s = origin + reverse(origin);
2. make next[] array of s in KMP algorithm. Then next[s.length] will be the k.
3. return origin.length - k
For example:
The origin string is abacd, then s=abacddcaba, then next[s.length] will be 3.
I think we need a max-heap to store the character frequency. And we know the total count.
0. check the max frequency is no more than (total + 1) / 2
1. Every time we get the top 2 frequency(f1, f2), and then f1-1, f2-1, total - 2. Then put f1, f2 to the heap, go to 1.
just iterate is ok.
Create a class BSTInOrderIterator
class BSTInOrderIterator {
BSTNode root;
Stack<BSTNode> s;
public BSTInOrderIterator(BSTNode root) {}
boolean hasNext();
BSTNode next();
}
just implement the inorder traversal in iterator.
Then you can initializes two instance and compare.
RepHi, I’m Jamie from the Portsmouth USA and I am working as an account manager. I work for a ...
Repnatetouche, Applications Developer at Alcatel Lucent
My name is NateTouche . I currently live in Seattle . One desire that has always been a constant since As a ...
I have two solution: merge sort or binary index tree.
- sakar2003 January 05, 2016