Google Interview find the longest substring T that contains m distinct characters

May 5, 2016 by omt

Given a string, find the longest substring T that contains m distinct characters. (need O(n) solution)

Input : omtomsairam
Output: omtsair

public class LongSubStringWithUniqueChar {

	private static boolean[] cache = new boolean[256];

	public static void main(String args[]) {
		System.out.println("Large Substring with distinct characters :" + getLargestSubString("omtomsairam"));
	}

	public static String getLargestSubString(String s) {
		StringBuilder result = new StringBuilder();
		generateLargestSubString(s, result);
		return result.toString();
	}

	public static void generateLargestSubString(String s, StringBuilder result) {

		if (s.length() > 0) {
			char c = s.charAt(0);
			if (!cache) {
				cache = true;
				result.append(c);
			}

			generateLargestSubString(s.substring(1), result);
		}
	}

}