HG
BAN USERWe can simply iterate from both sides and count the non-matching occurrences
public class Palindrome {
static boolean isKthPalindrome(String s, int k) {
if (s == null)
return false;
if (s.length() == 1)
return true;
char[] chars = s.toCharArray();
int count = 0;
for (int i = 0, j = chars.length - 1; j > i;) {
if (chars[i] == chars[j]) {
i++;
j--;
continue;
}
if (count == k)
return false;
count++;
if (i + 1 < j && chars[i + 1] == chars[j]) {
i++;
} else {
j--;
}
}
return true;
}
static void printIsKthPalindrome(String s, int k) {
boolean ret = isKthPalindrome(s, k);
System.out.println(s + " : " + (ret ? "YES" : "NO"));
}
public static void main(String[] args) {
printIsKthPalindrome("axbcybas", 3);
}
}
We can use max heap to keep track of top k elements between a and b. If the size increases beyond k, remove head. In the end head is the k-th element we need. This will be done in O(m log(m) ) time where m = b-a. If the sub-range is small compared to original array, then this is good. Space is O(k). Assuming k << n where n is total size of array, this solutions looks good.
public class GetKth {
int[] array;
public GetKth(int [] input) {
this.array = input;
}
int request(int a, int b, int k) {
Comparator<Integer> comp = new Comparator<Integer>() {
public int compare(Integer o1, Integer o2) {
return o2.compareTo(o1);
}
};
PriorityQueue<Integer> heap = new PriorityQueue<>(k+1, comp);
for(int i = a; i < b; i++) {
heap.add(array[i]);
if(heap.size() > k) {
heap.remove();
}
}
return heap.peek();
}
public static void main(String[] args) {
int [] array = new int [] {3,4,5,0,1,2};
GetKth prog = new GetKth(array);
System.out.println("request returned: " + prog.request(2, 5, 2));
}
}
- Run through String T and create a map with all characters
- Run through String S and add count of the characters in map
- Run through beginning of S with idx i and move ahead until count of a char in map is 1. Then move backwards with idx j until a char in map reaches 1 (decrement count if not 1).
- Save substring S(i,j)
Repeat above steps but in this case first find j' and then i'
- Save substring S(i',j')
Result is min of [S(i,j) , S(i',j') ]
// Complexity Time : O(2T+4S)=O(T+S) space : O(T)
- HG November 15, 2015