Irit
BAN USERO(n log n) Java solution with TreeSet.tailSet():
public static List<Integer> solution(int[] nums) {
LinkedList<Integer> result = new LinkedList<Integer>();
TreeSet<Integer> set = new TreeSet<Integer>();
for(int i=nums.length-1; i >= 0; i--) {
Set<Integer> larger = set.tailSet(nums[i], false);
result.addFirst(larger.size());
set.add(nums[i]);
}
return result;
}
public static boolean solution(int[] nums, int target) {
if(nums.length == 0) {
return target == 0;
}
int start = 0;
int end = 0;
int sum = nums[0];
if (sum == target) {
return true;
}
while(end < nums.length) {
if(sum > target) {
sum -= nums[start];
start++;
} else {
end++;
if(end < nums.length) {
sum += nums[end];
}
}
if (sum == target) {
return true;
}
}
return false;
}
O(n) solution, with comments:
public class Main {
public static void main(String args[]) {
System.out.println(minCoveringSubString("aabcbcdbca"));
}
private static class Interval {
int start, end;
public Interval(int start, int end) {
this.start = start; // inclusive
this.end = end; // exclusive
}
int getLength() {
return end-start;
}
}
private static String minCoveringSubString(String s) {
// FIND SET OF CHARACTERS
Set<Character> characters = new HashSet<Character>();
for (int i = 0; i < s.length(); i++) {
characters.add(s.charAt(i));
}
// ITERATE OVER STRING.
Interval minInterval = new Interval(0, s.length() - 1);
Map<Character, Integer> lastIndex = new HashMap<Character, Integer>();
for (int i = 0; i < s.length(); i++) {
char ch = s.charAt(i);
lastIndex.put(ch, i); // REMEMBER LAST INDEX OF EACH CHARACTER (SO FAR).
if (lastIndex.size() == characters.size()) { // SEEN ALL CHARACTERS
// HOW FAR BACK FROM i DO WE NEED TO GO TO COVER ALL CHARACTERS?
int maxDistance = 0;
for (Map.Entry<Character, Integer> entry : lastIndex.entrySet()) {
maxDistance = Math.max(maxDistance, i-entry.getValue());
}
if (maxDistance < minInterval.getLength()) {
// THIS INTERVAL ID BETTER THAN THE PREVIOUS MIN
minInterval = new Interval(i - maxDistance, i+1);
}
}
}
return s.substring(minInterval.start, minInterval.end);
}
}
public class Main {
public static void main(String args[]) {
System.out.println(uniqueMinLex("cbacdcbc"));
}
private static String uniqueMinLex(String s) {
// FIRST PASS: find the last index of each character
Map<Character, Integer> lastIndex = new HashMap<Character, Integer>();
Set<Character> included = new HashSet<Character>();
for(int i=0;i<s.length();i++) {
lastIndex.put(s.charAt(i), i);
}
// SECOND PASS: BUILD THE SOLUTION IN A STACK
StringBuilder sb = new StringBuilder();
for(int i=0;i<s.length();i++) {
char ch = s.charAt(i);
// POP FROM STACK CHARS LARGER THAN CH IF THERE WILL BE MORE OF THEM
while(
sb.length() > 0 && lastChar(sb) > ch // CH IS SMALLER THAN TOP OF STACK
&&
lastIndex.get(lastChar(sb)) > i) { // THERE WILL BE MORE OF THE CHAR AT TOP OF STACK
included.remove(lastChar(sb));
sb.delete(sb.length()-1, sb.length());
}
if(! included.contains(ch)) {
// CH IS NOT IN SOLUTION YET - ADD IT
sb.append(ch);
included.add(ch);
}
}
return sb.toString();
}
private static char lastChar(StringBuilder sb) {
return sb.charAt(sb.length()-1);
}
}
In the first pass, find for each character c the last occurrence of c in the input.
In the second pass, build a the solution as follows:
Put the first character of the input in the solution. Then, for each character c of the input:
if c is not already in the solution: let c' be the last character of the solution so far. while (c' > c and last occurrence of c' is yet to be seen) remove c' from the candidate solution. Then put c at the end of the solution.
Actually it seems that size() on a tailSet takes time linear in the size of the set, so this is not n log n. It's n^2.
- Irit October 28, 2015