Tag Archives: string

Longest palindrome starting from left side

Given a string, find the longest length of palindrome starting from the left. For example: abaeab, the longest from left is aba, so return 3. abcbaef, the longest from left is abcba, so return 5. ababa, the longest from left is ababa, so return 5. One of the solution is to use rolling hash, which… Read More »

minimum consecutive sub-string of S containing T

source: http://careercup.com/question?id=4855286160424960 Given a random string S and another string T with unique elements,. find the minimum consecutive sub-string of S such that it contains all the elements in T example: S=’adobecodebanc’ T=’abc’ answer=’banc” The idea is to maintain a double-linked-list. For each character in T, there is an element in double-linked-list. Every time, head has… Read More »

Minimum palindrome partition

One traditional question is to find the longest palindrome in a string. This has 3 ways to solve: 1. For each element, use 2 pointers to move to left and right. And find the furthest it can move. 2. Use lcs to find the longest common substring between string and reversed-string. Take “abccbd” as example, we… Read More »

Longest palindrome in a string

The problem is from a post on mitbbs: http://www.mitbbs.com/article_t/CS/31217531.html For example, longest palindrome in “animal” is “ana”, then return 3. Longest palindrome of “sfinished” is “sinis”, so return 5. This is actually a dp problem for longest common substring. We just easily find the longest common substring between “animal” with “lamina”, that will be the result. Check my… Read More »

Find longest substring without repeating

http://www.geeksforgeeks.org/amazon-interview-experience-set-149-campus-internship/ Round3, Q1 Given a string, find the longest substring without repeating characters. For example, the longest substrings without repeating characters for “ABDEFGABEF” are “BDEFGA” and “DEFGAB”. Instead of using a array for all 26 alphabets, I use hashmap to store the char which are already read. /* * http://www.geeksforgeeks.org/amazon-interview-experience-set-149-campus-internship/ * Round3, Q1 * Given a… Read More »

Find max difference two elements

http://www.geeksforgeeks.org/amazon-interview-experience-set-149-campus-internship/ /*  * Q2. Given an array arr[] of integers, find out the maximum difference between any  * two elements such that larger element appears after the smaller number in arr[].  * Print the indices of the two elements also.  * Example: If array is [2, 3, 10, 6, 4, 8, 1] then returned value… Read More »

Find TopK value, by small heap

This is the code to get top k values from a input. /*  * Get the Top Largest K values from small heap  */ public class TopK {     public static void main(String[] args) {         int[] array = {5, 13,10,12,15,11, 8,23, 40, 16, 83, 23, 31, 73, 59, 25, 75};         findTopK(array,… Read More »