Skip to content

Instantly share code, notes, and snippets.

@RichardCSantana-zz
Last active April 12, 2016 18:39
Show Gist options
  • Save RichardCSantana-zz/155cf2484f8bd1dc18cd2efb374ac04d to your computer and use it in GitHub Desktop.
Save RichardCSantana-zz/155cf2484f8bd1dc18cd2efb374ac04d to your computer and use it in GitHub Desktop.
package com.example;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
/**
* Solution for http://blog.gainlo.co/index.php/2016/04/12/find-the-longest-substring-with-k-unique-characters/
* @author richardsantana
*/
public class Solver {
public String getSubstring(String value, int uniqueChars) {
Grouping grouping = new Grouping(uniqueChars);
for (char character : value.toCharArray()) {
String representation = new String().valueOf(character);
grouping.addChar(representation);
}
return grouping.getGreatest().getString();
}
class Grouping {
private List<Structure> structures;
private Set<String> unique;
private Structure greatest;
private int maxSize;
public Grouping(int maxSize) {
this.structures = new ArrayList<>();
this.unique = new HashSet<>();
this.maxSize = maxSize;
this.greatest = new Structure(this.maxSize);
}
public void addChar(String character) {
if (!unique.contains(character)) {
structures.add(new Structure(this.maxSize));
unique.add(character);
}
structures.stream().forEach(structure -> {
structure.addChar(character);
if (structure.getSize() > greatest.getSize()) {
this.greatest = structure;
}
});
}
public Structure getGreatest() {
return this.greatest;
}
}
class Structure {
private Set<String> unique;
private int total;
private StringBuilder stringBuilder;
private int maxSize;
public Structure(int maxSize) {
this.unique = new HashSet<>();
stringBuilder = new StringBuilder();
this.maxSize = maxSize;
}
public String getString() {
return this.stringBuilder.toString();
}
public void addChar(String string) {
if (!containsChar(string)) {
this.unique.add(string);
total++;
}
if (total <= maxSize) {
stringBuilder.append(string);
}
}
public int getSize() {
return stringBuilder.length();
}
public boolean containsChar(String string) {
return this.unique.contains(string);
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment