Longest substring with 2 unique characters.

Q: Find the longest substring with at most two unique characters(ASCII) in a given string .

eg
input aabbccccceeedd
return ccccceee

We create a set of length 256 to keep the last index from the left. Whenever we reach a new character and count is still less than or equal to 2 we check if the current substring length is greater than the previous result. If it is we update the result as the current longest substring.

import java.util.Arrays;

public class Problem {

	public static String longestTwoUnique(String s) {
		char str[] = s.toCharArray();
		int[] set = new int[256];
		Arrays.fill(set, -1);
		int i = 0, j = 0;
		String res = "";
		int count = 0;
		while (j < s.length()) {
			if (set[str[j]] == -1) {
				set[str[j]] = j;
				count++;
				if (res.length() <= j - i)
					res = s.substring(i, j);
				if (count > 2) {
					count--;
					int nextI = set[str[i]];
					set[str[i]] = -1;
					i = nextI + 1;
				}
			} else {
				set[str[j]] = j;
				if (res.length() <= j - i)
					res = s.substring(i, j);
			}
			j++;
		}
		if (count <= 2 && res.length() <= j - i)
			res = s.substring(i, j);
		return res;
	}

	public static void main(String args[]) {
		System.out.println("longest string"
				+ longestTwoUnique("aabbccccceeedd"));

	}
}

Find element in bitonic array

Given an array which is monotonically increasing and then decreasing . Write an algorithm to search for a given element. Expected algorithm O(Log n)

An array of number is bitonic if it consists of a strictly increasing sequence followed by a strictly decreasing sequence. We can solve the problem in 3logN comparisons by finding the maximum in the array and then doing two binary searches, one on the increasing and one on the decreasing sequence. The maximum can be found in Log N comparisons using binary search. Each step compares two adjacent numbers A[i] and A[i+1]. If hey are equal, they are both maximum. If A[i] is smaller, we restrict the search to indices at most i, if A[i+1] is bigger, we restrict the search to indices greater than i.

 

public static int getMaximumElement(int a[], int low, int high)
	{
		if(low == high) return high;
		int mid = low + (high - low)/2;
		if(a[mid] < a[mid+1])
			return getMaximumElement(a, mid+1, high);
		else if(a[mid] > a[mid+1])
			return getMaximumElement(a, low, mid-1);
		else return mid;
	}