Skip to content

Instantly share code, notes, and snippets.

@steghio
Last active September 15, 2021 09:13
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save steghio/2855fc32d2b0cd226b2117cd3fc43154 to your computer and use it in GitHub Desktop.
String utilities
package com.blogspot.groglogs.test.stringutils;
import com.blogspot.groglogs.stringutils.StringUtils;
import org.junit.Test;
import static org.junit.Assert.assertEquals;
public class BreakPalindromeJTests {
String input, expected;
@Test
public void nullEmpty() {
input = null;
expected = "";
assertEquals("null", expected, StringUtils.breakPalindrome(input));
input = "";
expected = "";
assertEquals("empty", expected, StringUtils.breakPalindrome(input));
}
@Test
public void oneChar() {
input = "a";
expected = "";
assertEquals("a", expected, StringUtils.breakPalindrome(input));
}
@Test
public void twoChar() {
input = "aa";
expected = "ab";
assertEquals("aa", expected, StringUtils.breakPalindrome(input));
input = "bb";
expected = "ab";
assertEquals("bb", expected, StringUtils.breakPalindrome(input));
}
@Test
public void threeChar() {
input = "aaa";
expected = "aab";
assertEquals("aaa", expected, StringUtils.breakPalindrome(input));
input = "aba";
expected = "abb";
assertEquals("aba", expected, StringUtils.breakPalindrome(input));
input = "bbb";
expected = "abb";
assertEquals("bbb", expected, StringUtils.breakPalindrome(input));
}
@Test
public void sample() {
input = "abba";
expected = "aaba";
assertEquals("abba", expected, StringUtils.breakPalindrome(input));
input = "aaaa";
expected = "aaab";
assertEquals("aaaa", expected, StringUtils.breakPalindrome(input));
input = "abbba";
expected = "aabba";
assertEquals("abbba", expected, StringUtils.breakPalindrome(input));
input = "aaaaa";
expected = "aaaab";
assertEquals("aaaaa", expected, StringUtils.breakPalindrome(input));
input = "aabaa";
expected = "aabab";
assertEquals("aabaa", expected, StringUtils.breakPalindrome(input));
}
}
package com.blogspot.groglogs.test.stringutils;
import com.blogspot.groglogs.stringutils.StringUtils;
import org.junit.Test;
import static org.junit.Assert.assertFalse;
import static org.junit.Assert.assertTrue;
public class CheckBuddyStringsJTests {
String a, b;
@Test
public void nullEmpty() {
a = null;
b = null;
assertFalse("null", StringUtils.checkBuddyStrings(a, b));
a = "";
b = "";
assertFalse("empty", StringUtils.checkBuddyStrings(a, b));
}
@Test
public void oneChar() {
a = "a";
b = "b";
assertFalse("one char", StringUtils.checkBuddyStrings(a, b));
}
@Test
public void differentLength() {
a = "aa";
b = "bbb";
assertFalse("different length", StringUtils.checkBuddyStrings(a, b));
}
@Test
public void canSwap() {
a = "aa";
b = "aa";
assertTrue("aa,aa", StringUtils.checkBuddyStrings(a, b));
a = "aba";
b = "aba";
assertTrue("aba,aba", StringUtils.checkBuddyStrings(a, b));
}
@Test
public void cannotSwap() {
a = "ab";
b = "ab";
assertFalse("ab,ab", StringUtils.checkBuddyStrings(a, b));
a = "abc";
b = "abc";
assertFalse("abc,abc", StringUtils.checkBuddyStrings(a, b));
a = "abc";
b = "abd";
assertFalse("abc,abd", StringUtils.checkBuddyStrings(a, b));
}
@Test
public void mustSwap() {
a = "ab";
b = "ba";
assertTrue("ab,ba", StringUtils.checkBuddyStrings(a, b));
}
@Test
public void sample() {
a = "aaaaaaabc";
b = "aaaaaaacb";
assertTrue("aaaaaaabc,aaaaaaacb", StringUtils.checkBuddyStrings(a, b));
a = "aaaaaabbc";
b = "aaaaaaacb";
assertFalse("aaaaaabbc,aaaaaaacb", StringUtils.checkBuddyStrings(a, b));
}
}
package com.blogspot.groglogs.test.stringutils;
import org.junit.Test;
import com.blogspot.groglogs.stringutils.StringUtils;
import static org.junit.Assert.assertEquals;
public class CompressJTests {
String input, output;
@Test
//null or empty
public void nullEmpty() {
input = null;
output = null;
assertEquals("null string expected null", output, StringUtils.stringCompress(input));
input = "";
output = "";
assertEquals("empty string expected empty", output, StringUtils.stringCompress(input));
input = new String();
output = new String();
assertEquals("new string expected new String", output, StringUtils.stringCompress(input));
}
@Test
public void noCompress() {
input = "abcdefg";
output = "abcdefg";
assertEquals("abcdefg string expected abcdefg", output, StringUtils.stringCompress(input));
input = "aaabcdefg";
output = "aaabcdefg";
assertEquals("aaabcdefg string expected aaabcdefg", output, StringUtils.stringCompress(input));
}
@Test
public void withCompress() {
input = "aaaaaahhtt";
output = "a6h2t2";
assertEquals("aaaaaahhtt string expected a6h2t2", output, StringUtils.stringCompress(input));
input = " ";
output = " 3";
assertEquals(" string expected 3", output, StringUtils.stringCompress(input));
input = "AAAAAAA!!bcdefg MMMMM";
output = "A7!2b1c1d1e1f1g1 2M5";
assertEquals("AAAAAAA!!bcdefg MMMMM string expected A7!2b1c1d1e1f1g1 2M5", output, StringUtils.stringCompress(input));
}
}
package com.blogspot.groglogs.test.stringutils;
import com.blogspot.groglogs.stringutils.StringUtils;
import org.junit.Test;
import static org.junit.Assert.assertEquals;
public class CountWaysToDecodeJTests {
String s;
@Test
public void nullEmpty() {
s = null;
assertEquals("null input", 0, StringUtils.countWaysToDecode(s));
s = "";
assertEquals("empty input", 0, StringUtils.countWaysToDecode(s));
}
@Test(expected = IllegalArgumentException.class)
public void charactersInInput(){
s = "c";
StringUtils.countWaysToDecode(s);
}
@Test(expected = IllegalArgumentException.class)
public void charactersInInputAfterBeginning(){
s = "1c";
StringUtils.countWaysToDecode(s);
}
@Test(expected = IllegalArgumentException.class)
public void startsWithZero() {
s = "0";
StringUtils.countWaysToDecode(s);
}
@Test(expected = IllegalArgumentException.class)
public void doubleZero() {
s = "00";
StringUtils.countWaysToDecode(s);
}
@Test(expected = IllegalArgumentException.class)
public void zeroInWrongPlace() {
s = "06";
StringUtils.countWaysToDecode(s);
}
@Test(expected = IllegalArgumentException.class)
public void invalidZero() {
s = "50";
StringUtils.countWaysToDecode(s);
}
@Test
public void simpleValues() {
s = "1";
assertEquals("one digit input", 1, StringUtils.countWaysToDecode(s));
s = "55";
assertEquals("two digit single value input", 1, StringUtils.countWaysToDecode(s));
s = "10";
assertEquals("two digit single value with 0 input", 1, StringUtils.countWaysToDecode(s));
s = "22";
assertEquals("two digit double value input", 2, StringUtils.countWaysToDecode(s));
}
@Test
public void zeros() {
s = "110";
assertEquals("110", 1, StringUtils.countWaysToDecode(s));
s = "16205";
assertEquals("16205", 2, StringUtils.countWaysToDecode(s));
s = "20114";
assertEquals("20114", 3, StringUtils.countWaysToDecode(s));
s = "1201234";
assertEquals("1201234", 3, StringUtils.countWaysToDecode(s));
s = "2101";
assertEquals("2101", 1, StringUtils.countWaysToDecode(s));
}
@Test
public void sampleValues() {
s = "111";
assertEquals("111", 3, StringUtils.countWaysToDecode(s));
s = "25114";
assertEquals("25114", 6, StringUtils.countWaysToDecode(s));
s = "1111111111";
assertEquals("1111111111", 89, StringUtils.countWaysToDecode(s));
s = "3333333333";
assertEquals("3333333333", 1, StringUtils.countWaysToDecode(s));
}
}
package com.blogspot.groglogs.test.stringutils;
import com.blogspot.groglogs.stringutils.StringUtils;
import org.junit.Test;
import static org.junit.Assert.assertEquals;
public class DecodeStringJTests {
String s, expected;
@Test
public void nullEmpty() {
s = null;
expected = "";
assertEquals("null", expected, StringUtils.decodeString(s));
s = "";
expected = "";
assertEquals("empty", expected, StringUtils.decodeString(s));
}
@Test
public void simpleString() {
s = "abc";
expected = s;
assertEquals("abc", expected, StringUtils.decodeString(s));
}
@Test
public void repetitions() {
s = "1[a]";
expected = "a";
assertEquals("1[a]", expected, StringUtils.decodeString(s));
s = "2[a]";
expected = "aa";
assertEquals("2[a]", expected, StringUtils.decodeString(s));
s = "b1[a]";
expected = "ba";
assertEquals("b1[a]", expected, StringUtils.decodeString(s));
s = "b2[a]";
expected = "baa";
assertEquals("b2[a]", expected, StringUtils.decodeString(s));
s = "b1[a]c";
expected = "bac";
assertEquals("b1[a]c", expected, StringUtils.decodeString(s));
s = "b2[a]c";
expected = "baac";
assertEquals("b2[a]c", expected, StringUtils.decodeString(s));
s = "1[asd]";
expected = "asd";
assertEquals("1[asd]", expected, StringUtils.decodeString(s));
s = "2[asd]";
expected = "asdasd";
assertEquals("2[asd]", expected, StringUtils.decodeString(s));
}
@Test
public void nestedRepetitions() {
s = "1[1[a]]";
expected = "a";
assertEquals("1[1[a]]", expected, StringUtils.decodeString(s));
s = "2[2[a]]";
expected = "aaaa";
assertEquals("2[2[a]]", expected, StringUtils.decodeString(s));
s = "b1[1[a]]";
expected = "ba";
assertEquals("b1[1[a]]", expected, StringUtils.decodeString(s));
s = "b2[2[a]]";
expected = "baaaa";
assertEquals("b2[2[a]]", expected, StringUtils.decodeString(s));
s = "b1[1[a]]c";
expected = "bac";
assertEquals("b1[1[a]]c", expected, StringUtils.decodeString(s));
s = "b2[2[a]]c";
expected = "baaaac";
assertEquals("b2[2[a]]c", expected, StringUtils.decodeString(s));
s = "1[1[asd]]";
expected = "asd";
assertEquals("1[1[asd]]", expected, StringUtils.decodeString(s));
s = "2[2[asd]]";
expected = "asdasdasdasd";
assertEquals("2[2[asd]]", expected, StringUtils.decodeString(s));
}
@Test
public void sequenceRepetitions() {
s = "1[a]1[b]";
expected = "ab";
assertEquals("1[a]1[b]", expected, StringUtils.decodeString(s));
s = "2[a]2[b]";
expected = "aabb";
assertEquals("2[a]2[b]", expected, StringUtils.decodeString(s));
s = "b1[a]1[b]";
expected = "bab";
assertEquals("b1[a]1[b]", expected, StringUtils.decodeString(s));
s = "b2[a]2[b]";
expected = "baabb";
assertEquals("b2[a]2[b]", expected, StringUtils.decodeString(s));
s = "b1[a]c1[b]";
expected = "bacb";
assertEquals("b1[a]c1[b]", expected, StringUtils.decodeString(s));
s = "b2[a]c2[b]";
expected = "baacbb";
assertEquals("b2[a]c2[b]", expected, StringUtils.decodeString(s));
s = "1[asd]1[lol]";
expected = "asdlol";
assertEquals("1[asd]1[lol]", expected, StringUtils.decodeString(s));
s = "2[asd]2[lol]";
expected = "asdasdlollol";
assertEquals("2[asd]2[lol]", expected, StringUtils.decodeString(s));
s = "2[asd]def2[lol]";
expected = "asdasddeflollol";
assertEquals("2[asd]def2[lol]", expected, StringUtils.decodeString(s));
s = "2[asd3[c]m]def2[lol]";
expected = "asdcccmasdcccmdeflollol";
assertEquals("2[asd3[c]m]def2[lol]", expected, StringUtils.decodeString(s));
}
@Test
public void sample() {
s = "3[z]2[2[y]pq4[2[jk]e1[f]]]ef";
expected = "zzzyypqjkjkefjkjkefjkjkefjkjkefyypqjkjkefjkjkefjkjkefjkjkefef";
assertEquals("3[z]2[2[y]pq4[2[jk]e1[f]]]ef", expected, StringUtils.decodeString(s));
}
}
package com.blogspot.groglogs.test.stringutils;
import com.blogspot.groglogs.stringutils.StringUtils;
import org.junit.Test;
import static org.junit.Assert.assertEquals;
public class DecompressJTests {
String input, output;
@Test
//null or empty
public void nullEmpty() {
input = null;
try{
output = StringUtils.decompress(input);
} catch(IllegalArgumentException e){
System.out.println("null string got IllegalArgumentException " + e.getMessage());
}
input = "";
try{
output = StringUtils.decompress(input);
} catch(IllegalArgumentException e){
System.out.println("empty string got IllegalArgumentException " + e.getMessage());
}
input = new String();
try{
output = StringUtils.decompress(input);
} catch(IllegalArgumentException e){
System.out.println("new string got IllegalArgumentException " + e.getMessage());
}
}
@Test
public void noCompress() {
input = "[abcdefg]";
output = "abcdefg";
assertEquals("[abcdefg] string expected abcdefg", output, StringUtils.decompress(input));
input = "[]";
output = "";
assertEquals("[] string expected empty", output, StringUtils.decompress(input));
input = "[][]";
output = "";
assertEquals("[][] string expected empty", output, StringUtils.decompress(input));
input = "1[aaabcdefg]";
output = "aaabcdefg";
assertEquals("1[aaabcdefg] string expected aaabcdefg", output, StringUtils.decompress(input));
}
@Test
public void zeroCompress() {
input = "0[abcdefg][aa]";
output = "aa";
assertEquals("0[abcdefg][aa] string expected aa", output, StringUtils.decompress(input));
input = "[aa]0[abcdefg]";
output = "aa";
assertEquals("[aa]0[abcdefg] string expected aa", output, StringUtils.decompress(input));
}
@Test
public void withCompress() {
input = "3[abc]4[ab]c";
output = "abcabcabcababababc";
assertEquals("3[abc]4[ab]c string expected abcabcabcababababc", output, StringUtils.decompress(input));
input = "2[3[a]b]";
output = "aaabaaab";
assertEquals("2[3[a]b] string expected aaabaaab", output, StringUtils.decompress(input));
input = "2[3[a]b][[cc]0[d]]";
output = "aaabaaabcc";
assertEquals("2[3[a]b][cc0[d]] string expected aaabaaabcc", output, StringUtils.decompress(input));
input = "c";
output = "c";
assertEquals("c string expected c", output, StringUtils.decompress(input));
input = "10[a]";
output = "aaaaaaaaaa";
assertEquals("10[a] string expected aaaaaaaaaa", output, StringUtils.decompress(input));
}
}
package com.blogspot.groglogs.test.stringutils;
import com.blogspot.groglogs.stringutils.StringUtils;
import org.junit.Test;
import static org.junit.Assert.assertEquals;
public class EditDistanceJTests {
String start, end;
int expected;
@Test
public void nullEmpty() {
start = null;
end = null;
expected = 0;
assertEquals("null", expected, StringUtils.editDistance(start, end));
start = "";
end = "";
expected = 0;
assertEquals("empty", expected, StringUtils.editDistance(start, end));
start = new String();
end = new String();
expected = 0;
assertEquals("empty constructor", expected, StringUtils.editDistance(start, end));
start = "";
end = new String();
expected = 0;
assertEquals("both empty", expected, StringUtils.editDistance(start, end));
start = null;
end = new String();
expected = 0;
assertEquals("one null one empty", expected, StringUtils.editDistance(start, end));
}
@Test
public void oneNullEmptyOneNot() {
start = null;
end = "asd";
expected = end.length();
assertEquals("null, asd", expected, StringUtils.editDistance(start, end));
start = "";
end = "asd";
expected = end.length();
assertEquals("empty, asd", expected, StringUtils.editDistance(start, end));
start = "asd";
end = null;
expected = start.length();
assertEquals("asd, null", expected, StringUtils.editDistance(start, end));
start = "asd";
end = "";
expected = start.length();
assertEquals("asd, empty", expected, StringUtils.editDistance(start, end));
}
@Test
public void sameLength(){
start = "asd";
end = "asd";
expected = 0;
assertEquals("same string", expected, StringUtils.editDistance(start, end));
start = "lol";
end = "asd";
expected = start.length();
assertEquals("all different string", expected, StringUtils.editDistance(start, end));
}
@Test
public void differentLength(){
start = "asda";
end = "asd";
expected = 1;
assertEquals("same substring", expected, StringUtils.editDistance(start, end));
start = "loll";
end = "asd";
expected = start.length();
assertEquals("all different strings", expected, StringUtils.editDistance(start, end));
}
@Test
public void sample(){
start = "casar";
end = "ciao";
expected = 3;
assertEquals("casar,ciao", expected, StringUtils.editDistance(start, end));
start = "biting";
end = "sitting";
expected = 2;
assertEquals("biting,sitting", expected, StringUtils.editDistance(start, end));
}
}
package com.blogspot.groglogs.test.stringutils;
import com.blogspot.groglogs.stringutils.StringUtils;
import org.junit.Test;
import static org.junit.Assert.assertEquals;
public class EditDistanceWagnerFischerJTests {
String start, end;
int expected;
@Test
public void nullEmpty() {
start = null;
end = null;
expected = 0;
assertEquals("null", expected, StringUtils.editDistanceWagnerFischer(start, end));
start = "";
end = "";
expected = 0;
assertEquals("empty", expected, StringUtils.editDistanceWagnerFischer(start, end));
start = new String();
end = new String();
expected = 0;
assertEquals("empty constructor", expected, StringUtils.editDistanceWagnerFischer(start, end));
start = "";
end = new String();
expected = 0;
assertEquals("both empty", expected, StringUtils.editDistanceWagnerFischer(start, end));
start = null;
end = new String();
expected = 0;
assertEquals("one null one empty", expected, StringUtils.editDistanceWagnerFischer(start, end));
}
@Test
public void oneNullEmptyOneNot() {
start = null;
end = "asd";
expected = end.length();
assertEquals("null, asd", expected, StringUtils.editDistanceWagnerFischer(start, end));
start = "";
end = "asd";
expected = end.length();
assertEquals("empty, asd", expected, StringUtils.editDistanceWagnerFischer(start, end));
start = "asd";
end = null;
expected = start.length();
assertEquals("asd, null", expected, StringUtils.editDistanceWagnerFischer(start, end));
start = "asd";
end = "";
expected = start.length();
assertEquals("asd, empty", expected, StringUtils.editDistanceWagnerFischer(start, end));
}
@Test
public void sameLength(){
start = "asd";
end = "asd";
expected = 0;
assertEquals("same string", expected, StringUtils.editDistanceWagnerFischer(start, end));
start = "lol";
end = "asd";
expected = start.length();
assertEquals("all different string", expected, StringUtils.editDistanceWagnerFischer(start, end));
}
@Test
public void differentLength(){
start = "asda";
end = "asd";
expected = 1;
assertEquals("same substring", expected, StringUtils.editDistanceWagnerFischer(start, end));
start = "loll";
end = "asd";
expected = start.length();
assertEquals("all different strings", expected, StringUtils.editDistanceWagnerFischer(start, end));
}
@Test
public void sample(){
start = "casar";
end = "ciao";
expected = 3;
assertEquals("casar,ciao", expected, StringUtils.editDistanceWagnerFischer(start, end));
start = "biting";
end = "sitting";
expected = 2;
assertEquals("biting,sitting", expected, StringUtils.editDistanceWagnerFischer(start, end));
}
}
package com.blogspot.groglogs.structures;
public class Entry {
public char c;
public int count = 0;
@Override
public boolean equals(Object obj) {
if(obj == null) return false;
if(obj.getClass() != this.getClass()) return false;
Entry other = (Entry) obj;
return this.c == other.c && this.count == other.count;
}
}
package com.blogspot.groglogs.test.stringutils;
import com.blogspot.groglogs.stringutils.StringUtils;
import org.junit.Test;
import java.util.ArrayList;
import java.util.List;
import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertTrue;
public class FullJustifyJTests {
String[] words;
int size;
List<String> out, expected;
@Test
public void nullEmpty() {
words = null;
size = 16;
assertTrue("null", StringUtils.fullJustify(words, size).isEmpty());
words = new String[]{};
size = 16;
assertTrue("empty", StringUtils.fullJustify(words, size).isEmpty());
words = new String[]{"asd"};
size = 0;
assertTrue("0 size", StringUtils.fullJustify(words, size).isEmpty());
}
@Test
public void oneWord() {
words = new String[]{"asd"};
size = 3;
out = StringUtils.fullJustify(words, size);
expected = out;
assertEquals("size is correct", expected.size(), out.size());
for(int i = 0; i < out.size(); i++){
assertEquals("line is correct", expected.get(i), out.get(i));
}
words = new String[]{"asd"};
size = 4;
out = StringUtils.fullJustify(words, size);
expected = new ArrayList<>();
expected.add("asd ");
assertEquals("size is correct", expected.size(), out.size());
for(int i = 0; i < out.size(); i++){
assertEquals("line is correct", expected.get(i), out.get(i));
}
}
@Test
public void oneLine() {
words = new String[]{"asd", "lol"};
size = 7;
out = StringUtils.fullJustify(words, size);
expected = new ArrayList<>();
expected.add("asd lol");
assertEquals("size is correct", expected.size(), out.size());
for(int i = 0; i < out.size(); i++){
assertEquals("line is correct", expected.get(i), out.get(i));
}
words = new String[]{"asd", "lol"};
size = 8;
out = StringUtils.fullJustify(words, size);
expected = new ArrayList<>();
expected.add("asd lol ");
assertEquals("size is correct", expected.size(), out.size());
for(int i = 0; i < out.size(); i++){
assertEquals("line is correct", expected.get(i), out.get(i));
}
}
@Test
public void twoLine() {
words = new String[]{"asd", "lol"};
size = 3;
out = StringUtils.fullJustify(words, size);
expected = new ArrayList<>();
expected.add("asd");
expected.add("lol");
assertEquals("size is correct", expected.size(), out.size());
for(int i = 0; i < out.size(); i++){
assertEquals("line is correct", expected.get(i), out.get(i));
}
words = new String[]{"asd", "lol"};
size = 4;
out = StringUtils.fullJustify(words, size);
expected = new ArrayList<>();
expected.add("asd ");
expected.add("lol ");
assertEquals("size is correct", expected.size(), out.size());
for(int i = 0; i < out.size(); i++){
assertEquals("line is correct", expected.get(i), out.get(i));
}
}
@Test
public void sample() {
words = new String[]{"This", "is", "an", "example", "of", "text", "justification."};
size = 16;
out = StringUtils.fullJustify(words, size);
expected = new ArrayList<>();
expected.add("This is an");
expected.add("example of text");
expected.add("justification. ");
assertEquals("size is correct", expected.size(), out.size());
for(int i = 0; i < out.size(); i++){
assertEquals("line is correct", expected.get(i), out.get(i));
}
words = new String[]{"the", "quick", "brown", "fox", "jumps", "over", "the", "lazy", "dog"};
size = 16;
out = StringUtils.fullJustify(words, size);
expected = new ArrayList<>();
expected.add("the quick brown");
expected.add("fox jumps over");
expected.add("the lazy dog ");
assertEquals("size is correct", expected.size(), out.size());
for(int i = 0; i < out.size(); i++){
assertEquals("line is correct", expected.get(i), out.get(i));
}
}
}
package com.blogspot.groglogs.test.stringutils;
import com.blogspot.groglogs.stringutils.StringUtils;
import org.junit.Test;
import static org.junit.Assert.assertEquals;
public class GetShortestUniqueSubstringJTests {
char[] chars;
String s, expected;
@Test
public void nullEmpty() {
chars = null;
s = null;
expected = "";
assertEquals("null", expected, StringUtils.getShortestUniqueSubstring(chars, s));
chars = new char[]{};
s = "a";
expected = "";
assertEquals("empty chars", expected, StringUtils.getShortestUniqueSubstring(chars, s));
chars = new char[]{'c'};
s = "";
expected = "";
assertEquals("empty string", expected, StringUtils.getShortestUniqueSubstring(chars, s));
}
@Test
public void noCharInString() {
chars = new char[]{'c','a','b'};
s = "a";
expected = "";
assertEquals("too many chars", expected, StringUtils.getShortestUniqueSubstring(chars, s));
chars = new char[]{'c','a','b'};
s = "aaa";
expected = "";
assertEquals("char not in string", expected, StringUtils.getShortestUniqueSubstring(chars, s));
}
@Test
public void allCharsInString() {
chars = new char[]{'c','a','b'};
s = "bac";
expected = s;
assertEquals("chars are string", expected, StringUtils.getShortestUniqueSubstring(chars, s));
chars = new char[]{'c','a','b'};
s = "caabbac";
expected = "bac";
assertEquals("all chars in string", expected, StringUtils.getShortestUniqueSubstring(chars, s));
}
@Test
public void foreignCharsInString() {
chars = new char[]{'c','a','b'};
s = "cabdbac";
expected = "cab";
assertEquals("foreign char in string", expected, StringUtils.getShortestUniqueSubstring(chars, s));
chars = new char[]{'c'};
s = "dfghc";
expected = "c";
assertEquals("all foreign except last", expected, StringUtils.getShortestUniqueSubstring(chars, s));
}
@Test
public void sample() {
chars = new char[]{'x','y','z'};
s = "xyyzyzyx";
expected = "zyx";
assertEquals("foreign char in string", expected, StringUtils.getShortestUniqueSubstring(chars, s));
}
}
package com.blogspot.groglogs.test.stringutils;
import com.blogspot.groglogs.stringutils.StringUtils;
import org.junit.Test;
import java.util.ArrayList;
import java.util.List;
import static org.junit.Assert.assertEquals;
public class GroupAnagramsJTests {
String[] input;
List<List<String>> expected;
private void checkListEquals(List<List<String>> expected, List<List<String>> actual){
assertEquals("same size", expected.size(), actual.size());
for(int i = 0; i < expected.size(); i++){
List<String> ex = expected.get(i);
List<String> ac = actual.get(i);
for(int j = 0; j < ex.size(); j++){
assertEquals("same string", ex.get(j), ac.get(j));
}
}
}
@Test
public void nullEmpty() {
input = null;
expected = new ArrayList<>();
checkListEquals(expected, StringUtils.groupAnagrams(input));
input = new String[]{};
expected = new ArrayList<>();
checkListEquals(expected, StringUtils.groupAnagrams(input));
}
@Test
public void oneWord() {
input = new String[]{"asd"};
expected = new ArrayList<>();
List<String> ex = new ArrayList<>();
ex.add("asd");
expected.add(ex);
checkListEquals(expected, StringUtils.groupAnagrams(input));
}
@Test
public void anagramsSameLength() {
input = new String[]{"asd", "lol", "sda"};
expected = new ArrayList<>();
List<String> ex2 = new ArrayList<>();
ex2.add("lol");
expected.add(ex2);
List<String> ex = new ArrayList<>();
ex.add("asd");
ex.add("sda");
expected.add(ex);
checkListEquals(expected, StringUtils.groupAnagrams(input));
}
@Test
public void anagramsDifferentLength() {
input = new String[]{"asdd", "lol", "dsda", "asd", "dsa"};
expected = new ArrayList<>();
List<String> ex3 = new ArrayList<>();
ex3.add("asdd");
ex3.add("dsda");
expected.add(ex3);
List<String> ex2 = new ArrayList<>();
ex2.add("lol");
expected.add(ex2);
List<String> ex = new ArrayList<>();
ex.add("asd");
ex.add("dsa");
expected.add(ex);
checkListEquals(expected, StringUtils.groupAnagrams(input));
}
}
package com.blogspot.groglogs.test.stringutils;
import com.blogspot.groglogs.stringutils.StringUtils;
import org.junit.Test;
import static org.junit.Assert.assertEquals;
public class InterleavingJTests {
String a, b, c;
boolean output;
@Test
//null or empty input
public void nullEmpty() {
a = null;
b = null;
c = null;
output = true;
//all null
assertEquals("null, null, null", output, StringUtils.isInterleave(a, b, c));
assertEquals("null, null, null", output, StringUtils.findInterleaveNoDP(a, b, c));
a = "";
b = "";
c = "";
output = true;
//all empty
assertEquals("empty, empty, empty", output, StringUtils.isInterleave(a, b, c));
assertEquals("empty, empty, empty", output, StringUtils.findInterleaveNoDP(a, b, c));
a = null;
b = null;
c = "a";
output = false;
//a,b null
assertEquals("null, null, a", output, StringUtils.isInterleave(a, b, c));
assertEquals("null, null, a", output, StringUtils.findInterleaveNoDP(a, b, c));
a = null;
b = null;
c = "ab";
output = false;
//a,b null
assertEquals("null, null, ab", output, StringUtils.isInterleave(a, b, c));
assertEquals("null, null, ab", output, StringUtils.findInterleaveNoDP(a, b, c));
a = "";
b = "";
c = "a";
output = false;
//a,b empty
assertEquals("empty, empty, a", output, StringUtils.isInterleave(a, b, c));
assertEquals("empty, empty, a", output, StringUtils.findInterleaveNoDP(a, b, c));
a = "";
b = "";
c = "ab";
output = false;
//a,b empty
assertEquals("empty, empty, ab", output, StringUtils.isInterleave(a, b, c));
assertEquals("empty, empty, ab", output, StringUtils.findInterleaveNoDP(a, b, c));
a = "a";
b = null;
c = "a";
output = true;
//b null
assertEquals("a, null, a", output, StringUtils.isInterleave(a, b, c));
assertEquals("a, null, a", output, StringUtils.findInterleaveNoDP(a, b, c));
a = "ab";
b = null;
c = "ab";
output = true;
//b null
assertEquals("ab, null, ab", output, StringUtils.isInterleave(a, b, c));
assertEquals("ab, null, ab", output, StringUtils.findInterleaveNoDP(a, b, c));
a = "a";
b = null;
c = "b";
output = false;
//b null
assertEquals("a, null, b", output, StringUtils.isInterleave(a, b, c));
assertEquals("a, null, b", output, StringUtils.findInterleaveNoDP(a, b, c));
a = "ab";
b = null;
c = "ac";
output = false;
//b null
assertEquals("ab, null, ac", output, StringUtils.isInterleave(a, b, c));
assertEquals("ab, null, ac", output, StringUtils.findInterleaveNoDP(a, b, c));
a = "a";
b = "";
c = "a";
output = true;
//b empty
assertEquals("a, empty, a", output, StringUtils.isInterleave(a, b, c));
assertEquals("a, empty, a", output, StringUtils.findInterleaveNoDP(a, b, c));
a = "ab";
b = "";
c = "ab";
output = true;
//b empty
assertEquals("ab, empty, ab", output, StringUtils.isInterleave(a, b, c));
assertEquals("ab, empty, ab", output, StringUtils.findInterleaveNoDP(a, b, c));
a = "a";
b = "";
c = "c";
output = false;
//b empty
assertEquals("a, empty, c", output, StringUtils.isInterleave(a, b, c));
assertEquals("a, empty, c", output, StringUtils.findInterleaveNoDP(a, b, c));
a = "ab";
b = "";
c = "ac";
output = false;
//b empty
assertEquals("ab, empty, ac", output, StringUtils.isInterleave(a, b, c));
assertEquals("ab, empty, ac", output, StringUtils.findInterleaveNoDP(a, b, c));
a = null;
b = "a";
c = "a";
output = true;
//a null
assertEquals("null, a, a", output, StringUtils.isInterleave(a, b, c));
assertEquals("null, a, a", output, StringUtils.findInterleaveNoDP(a, b, c));
a = null;
b = "ab";
c = "ab";
output = true;
//a null
assertEquals("null, ab, ab", output, StringUtils.isInterleave(a, b, c));
assertEquals("null, ab, ab", output, StringUtils.findInterleaveNoDP(a, b, c));
a = "";
b = "a";
c = "a";
output = true;
//a empty
assertEquals("empty, a, a", output, StringUtils.isInterleave(a, b, c));
assertEquals("empty, a, a", output, StringUtils.findInterleaveNoDP(a, b, c));
a = "";
b = "ab";
c = "ab";
output = true;
//a empty
assertEquals("empty, ab, ab", output, StringUtils.isInterleave(a, b, c));
assertEquals("empty, ab, ab", output, StringUtils.findInterleaveNoDP(a, b, c));
a = null;
b = "a";
c = "c";
output = false;
//a null
assertEquals("null, a, c", output, StringUtils.isInterleave(a, b, c));
assertEquals("null, a, c", output, StringUtils.findInterleaveNoDP(a, b, c));
a = null;
b = "ab";
c = "ac";
output = false;
//a null
assertEquals("null, ab, ac", output, StringUtils.isInterleave(a, b, c));
assertEquals("null, ab, ac", output, StringUtils.findInterleaveNoDP(a, b, c));
a = "";
b = "a";
c = "c";
output = false;
//a empty
assertEquals("empty, a, c", output, StringUtils.isInterleave(a, b, c));
assertEquals("empty, a, c", output, StringUtils.findInterleaveNoDP(a, b, c));
a = "";
b = "ab";
c = "ac";
output = false;
//a empty
assertEquals("empty, ab, ac", output, StringUtils.isInterleave(a, b, c));
assertEquals("empty, ab, ac", output, StringUtils.findInterleaveNoDP(a, b, c));
}
@Test
//random
public void randomMatch() {
a = "xy";
b = "x";
c = "xxy";
output = true;
assertEquals("xy, x, xxy", output, StringUtils.isInterleave(a, b, c));
assertEquals("xy, x, xxy", output, StringUtils.findInterleaveNoDP(a, b, c));
a = "ABC";
b = "ACA";
c = "ABACCA";
output = true;
assertEquals("ABC, ACA, ABACCA", output, StringUtils.isInterleave(a, b, c));
assertEquals("ABC, ACA, ABACCA", output, StringUtils.findInterleaveNoDP(a, b, c));
a = "ABC";
b = "ACA";
c = "ABACAC";
output = true;
assertEquals("ABC, ACA, ABACAC", output, StringUtils.isInterleave(a, b, c));
assertEquals("ABC, ACA, ABACAC", output, StringUtils.findInterleaveNoDP(a, b, c));
a = "A";
b = "A";
c = "AA";
output = true;
assertEquals("A, A, AA", output, StringUtils.isInterleave(a, b, c));
assertEquals("A, A, AA", output, StringUtils.findInterleaveNoDP(a, b, c));
a = "AA";
b = "AA";
c = "AAAA";
output = true;
assertEquals("AA, AA, AAAA", output, StringUtils.isInterleave(a, b, c));
assertEquals("AA, AA, AAAA", output, StringUtils.findInterleaveNoDP(a, b, c));
a = "AAA";
b = "AAA";
c = "AAAAAA";
output = true;
assertEquals("AAA, AAA, AAAAAA", output, StringUtils.isInterleave(a, b, c));
assertEquals("AAA, AAA, AAAAAA", output, StringUtils.findInterleaveNoDP(a, b, c));
a = "AAAA";
b = "AAAA";
c = "AAAAAAAA";
output = true;
assertEquals("AAAA, AAAA, AAAAAAAA", output, StringUtils.isInterleave(a, b, c));
assertEquals("AAAA, AAAA, AAAAAAAA", output, StringUtils.findInterleaveNoDP(a, b, c));
a = "AB";
b = "CD";
c = "ABCD";
output = true;
assertEquals("AB, CD, ABCD", output, StringUtils.isInterleave(a, b, c));
assertEquals("AB, CD, ABCD", output, StringUtils.findInterleaveNoDP(a, b, c));
a = "AB";
b = "CD";
c = "CDAB";
output = true;
assertEquals("AB, CD, CDAB", output, StringUtils.isInterleave(a, b, c));
assertEquals("AB, CD, CDAB", output, StringUtils.findInterleaveNoDP(a, b, c));
a = "AB";
b = "CD";
c = "ACBD";
output = true;
assertEquals("AB, CD, ACBD", output, StringUtils.isInterleave(a, b, c));
assertEquals("AB, CD, ACBD", output, StringUtils.findInterleaveNoDP(a, b, c));
a = "AB";
b = "CD";
c = "ACDB";
output = true;
assertEquals("AB, CD, ACDB", output, StringUtils.isInterleave(a, b, c));
assertEquals("AB, CD, ACDB", output, StringUtils.findInterleaveNoDP(a, b, c));
a = "AB";
b = "CD";
c = "CADB";
output = true;
assertEquals("AB, CD, CADB", output, StringUtils.isInterleave(a, b, c));
assertEquals("AB, CD, CADB", output, StringUtils.findInterleaveNoDP(a, b, c));
}
@Test
//random
public void randomNotMatch() {
a = "yx";
b = "x";
c = "xxy";
output = false;
assertEquals("yx, x, xxy", output, StringUtils.isInterleave(a, b, c));
assertEquals("yx, x, xxy", output, StringUtils.findInterleaveNoDP(a, b, c));
a = "xxxxx";
b = "xxxxx";
c = "xxxxxxxxxy";
output = false;
assertEquals("xxxxx, xxxxx, xxxxxxxxxy", output, StringUtils.isInterleave(a, b, c));
assertEquals("xxxxx, xxxxx, xxxxxxxxxy", output, StringUtils.findInterleaveNoDP(a, b, c));
a = "xxxxxy";
b = "xxxxxy";
c = "xxxxxxxxxxxy";
output = false;
assertEquals("xxxxxy, xxxxxy, xxxxxxxxxxxy", output, StringUtils.isInterleave(a, b, c));
assertEquals("xxxxxy, xxxxxy, xxxxxxxxxxxy", output, StringUtils.findInterleaveNoDP(a, b, c));
a = "xxxxxy";
b = "xxxxxx";
c = "xxxxxxxxxxyy";
output = false;
assertEquals("xxxxxy, xxxxxx, xxxxxxxxxxyy", output, StringUtils.isInterleave(a, b, c));
assertEquals("xxxxxy, xxxxxx, xxxxxxxxxxyy", output, StringUtils.findInterleaveNoDP(a, b, c));
a = "ABC";
b = "ACA";
c = "ABAACC";
output = false;
assertEquals("ABC, ACA, ABAACC", output, StringUtils.isInterleave(a, b, c));
assertEquals("ABC, ACA, ABAACC", output, StringUtils.findInterleaveNoDP(a, b, c));
}
}
package com.blogspot.groglogs.test.stringutils;
import com.blogspot.groglogs.stringutils.StringUtils;
import org.junit.Test;
import static org.junit.Assert.assertFalse;
import static org.junit.Assert.assertTrue;
public class IsRotationJTests {
String s, rotated;
@Test
public void nullEmpty() {
s = null;
rotated = null;
assertTrue("null", StringUtils.isRotation(s, rotated));
s = "";
rotated = "";
assertTrue("empty", StringUtils.isRotation(s, rotated));
s = null;
rotated = "";
assertFalse("null,empty", StringUtils.isRotation(s, rotated));
s = "";
rotated = null;
assertFalse("empty,null", StringUtils.isRotation(s, rotated));
}
@Test
public void differentLength() {
s = "asd";
rotated = "a";
assertFalse("asd,a", StringUtils.isRotation(s, rotated));
}
@Test
public void noRotation() {
s = "asd";
rotated = "asf";
assertFalse("asd,asf", StringUtils.isRotation(s, rotated));
}
@Test
public void rotation() {
s = "asd";
rotated = "asd";
assertTrue("asd,asd", StringUtils.isRotation(s, rotated));
s = "asd";
rotated = "sda";
assertTrue("asd,sda", StringUtils.isRotation(s, rotated));
s = "asd";
rotated = "das";
assertTrue("asd,das", StringUtils.isRotation(s, rotated));
}
}
package com.blogspot.groglogs.test.stringutils;
import com.blogspot.groglogs.stringutils.StringUtils;
import org.junit.Test;
import java.util.LinkedList;
import java.util.List;
import static org.junit.Assert.assertArrayEquals;
import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertTrue;
public class KMPJTests {
String word, text;
int[] expected_table;
List<Integer> expected_matches, matches;
@Test
public void nullEmptyTable() {
word = null;
expected_table = new int[]{};
assertArrayEquals("null", expected_table, StringUtils.buildKMPTable(word));
word = "";
expected_table = new int[]{};
assertArrayEquals("empty", expected_table, StringUtils.buildKMPTable(word));
}
@Test
public void noPrefixesTable() {
word = "abc";
expected_table = new int[]{-1,0,0,0};
assertArrayEquals("no prefixes", expected_table, StringUtils.buildKMPTable(word));
}
@Test
public void allSameTable() {
word = "aaa";
expected_table = new int[]{-1,-1,-1,2};
assertArrayEquals("all same character", expected_table, StringUtils.buildKMPTable(word));
}
@Test
public void sampleTable() {
word = "abcdabd";
expected_table = new int[]{-1,0,0,0,-1,0,2,0};
assertArrayEquals("abcdabd", expected_table, StringUtils.buildKMPTable(word));
word = "abacababc";
expected_table = new int[]{-1,0,-1,1,-1,0,-1,3,2,0};
assertArrayEquals("abacababc", expected_table, StringUtils.buildKMPTable(word));
word = "participate in parachute";
expected_table = new int[]{-1,0,0,0,0,0,0,-1,0,2,0,0,0,0,0,-1,0,0,3,0,0,0,0,0,0 };
assertArrayEquals("participate in parachute", expected_table, StringUtils.buildKMPTable(word));
}
@Test
public void nullEmptySearch() {
word = null;
text = null;
expected_matches = new LinkedList<>();
assertTrue("null", StringUtils.searchSubstringKMP(text, word, true).isEmpty());
word = "";
text = "";
expected_matches = new LinkedList<>();
assertTrue("empty", StringUtils.searchSubstringKMP(text, word, true).isEmpty());
}
@Test
public void noMatch() {
word = "asd";
text = "a";
expected_matches = new LinkedList<>();
assertTrue("word too long", StringUtils.searchSubstringKMP(text, word, true).isEmpty());
word = "asd";
text = "ghjghjhgj";
expected_matches = new LinkedList<>();
assertTrue("no match", StringUtils.searchSubstringKMP(text, word, true).isEmpty());
}
@Test
public void allMatch() {
word = "a";
text = "aaa";
expected_matches = new LinkedList<>();
expected_matches.add(0);
expected_matches.add(1);
expected_matches.add(2);
matches = StringUtils.searchSubstringKMP(text, word, true);
assertEquals("all match", expected_matches.size(), matches.size());
for(int i = 0; i < expected_matches.size(); i++){
assertEquals("match is correct", expected_matches.get(i), matches.get(i));
}
word = "a";
text = "a";
expected_matches = new LinkedList<>();
expected_matches.add(0);
matches = StringUtils.searchSubstringKMP(text, word, true);
assertEquals("one match", expected_matches.size(), matches.size());
for(int i = 0; i < expected_matches.size(); i++){
assertEquals("match is correct", expected_matches.get(i), matches.get(i));
}
}
@Test
public void sample() {
word = "ABCDABD";
text = "ABC ABCDAB ABCDABCDABDE";
expected_matches = new LinkedList<>();
expected_matches.add(15);
matches = StringUtils.searchSubstringKMP(text, word, true);
assertEquals("ABCDABD, ABC ABCDAB ABCDABCDABDE", expected_matches.size(), matches.size());
for(int i = 0; i < expected_matches.size(); i++){
assertEquals("match is correct", expected_matches.get(i), matches.get(i));
}
word = "ABC";
text = "ABC ABCDAB ABCDABCDABDE";
expected_matches = new LinkedList<>();
expected_matches.add(0);
expected_matches.add(4);
expected_matches.add(11);
expected_matches.add(15);
matches = StringUtils.searchSubstringKMP(text, word, true);
assertEquals("ABC, ABC ABCDAB ABCDABCDABDE", expected_matches.size(), matches.size());
for(int i = 0; i < expected_matches.size(); i++){
assertEquals("match is correct", expected_matches.get(i), matches.get(i));
}
word = "ABC";
text = "ABC ABCDAB ABCDABCDABDE";
expected_matches = new LinkedList<>();
expected_matches.add(0);
matches = StringUtils.searchSubstringKMP(text, word, false);
assertEquals("ABC, ABC ABCDAB ABCDABCDABDE only first match", expected_matches.size(), matches.size());
for(int i = 0; i < expected_matches.size(); i++){
assertEquals("match is correct", expected_matches.get(i), matches.get(i));
}
}
}
package com.blogspot.groglogs.test.stringutils;
import com.blogspot.groglogs.stringutils.StringUtils;
import org.junit.Test;
import static org.junit.Assert.assertEquals;
public class LongestCommonSubstringJTests {
String s1, s2;
@Test
public void nullEmpty() {
s1 = null;
s2 = null;
assertEquals("both null", "", StringUtils.longestCommonSubstring(s1, s2));
s1 = null;
s2 = "";
assertEquals("s1 null s2 empty", "", StringUtils.longestCommonSubstring(s1, s2));
s1 = "";
s2 = null;
assertEquals("s2 null s1 empty", "", StringUtils.longestCommonSubstring(s1, s2));
s1 = "";
s2 = "";
assertEquals("both empty", "", StringUtils.longestCommonSubstring(s1, s2));
}
@Test
public void singleCharacter() {
s1 = "a";
s2 = "b";
assertEquals("different characters", "", StringUtils.longestCommonSubstring(s1, s2));
s1 = "a";
s2 = "";
assertEquals("one character and empty", "", StringUtils.longestCommonSubstring(s1, s2));
s1 = "a";
s2 = s1;
assertEquals("same character", s1, StringUtils.longestCommonSubstring(s1, s2));
}
@Test
public void repeatedCharacters() {
s1 = "aaaa";
s2 = "bab";
assertEquals("one match for repeated character", "a", StringUtils.longestCommonSubstring(s1, s2));
s1 = "aa";
s2 = "";
assertEquals("repeated characters and empty", "", StringUtils.longestCommonSubstring(s1, s2));
}
@Test
public void sameLength() {
s1 = "abcba";
s2 = s1;
assertEquals("same string", s1, StringUtils.longestCommonSubstring(s1, s2));
s1 = "abcba";
s2 = "bcbde";
assertEquals("partial match", "bcb", StringUtils.longestCommonSubstring(s1, s2));
s1 = "abcbadedf";
s2 = "bcbdedfab";
assertEquals("longer match last", "dedf", StringUtils.longestCommonSubstring(s1, s2));
s1 = "abcbaded";
s2 = "bcbdedab";
assertEquals("multiple matches same length ", "bcb", StringUtils.longestCommonSubstring(s1, s2));
}
@Test
public void differentLengths() {
s1 = "abcba";
s2 = "abcb";
assertEquals("whole s2 match", s2, StringUtils.longestCommonSubstring(s1, s2));
s1 = "abcba";
s2 = "dbcb";
assertEquals("partial match", "bcb", StringUtils.longestCommonSubstring(s1, s2));
s1 = "abcbadedf";
s2 = "bcbdedfg";
assertEquals("longer match last", "dedf", StringUtils.longestCommonSubstring(s1, s2));
s1 = "abcbaded";
s2 = "bcbded";
assertEquals("multiple matches same length ", "bcb", StringUtils.longestCommonSubstring(s1, s2));
}
}
package com.blogspot.groglogs.test.stringutils;
import com.blogspot.groglogs.stringutils.StringUtils;
import org.junit.Test;
import static org.junit.Assert.assertEquals;
public class LongestFilesystemPathJTests {
String input;
int expected;
@Test
public void nullEmpty() {
input = null;
expected = 0;
assertEquals("null", expected, StringUtils.longestFilesystemPath(input));
input = "";
expected = 0;
assertEquals("empty", expected, StringUtils.longestFilesystemPath(input));
}
@Test
public void noFile() {
input = "asd";
expected = 0;
assertEquals("no file simple", expected, StringUtils.longestFilesystemPath(input));
input = "asd\n\tlol";
expected = 0;
assertEquals("no file one level", expected, StringUtils.longestFilesystemPath(input));
input = "asd\n\tlol\n\t\tgg\n\tff";
expected = 0;
assertEquals("no file multiple levels", expected, StringUtils.longestFilesystemPath(input));
}
@Test
public void oneFile() {
input = "asd.txt";
expected = input.length();
assertEquals("one file", expected, StringUtils.longestFilesystemPath(input));
input = "asd\n\tlol.txt";
expected = 11; //asd/lol.txt
assertEquals("one file one level", expected, StringUtils.longestFilesystemPath(input));
input = "asd\n\tlol\n\t\tgg\n\tff\n\t\tlol.txt";
expected = 14; //asd/ff/lol.txt
assertEquals("one file multiple levels", expected, StringUtils.longestFilesystemPath(input));
}
@Test
public void longerFilename() {
input = "asd\n\tlol\n\t\tgg\n\tff\n\t\tlol.txt\n\t\tloll.txt";
expected = 15; //asd/ff/loll.txt
assertEquals("longer filename in same folder", expected, StringUtils.longestFilesystemPath(input));
input = "asd\n\tlol\n\t\tgg\n\t\taaaaa.txt\n\tff\n\t\tlol.txt\n\t\tloll.txt";
expected = 17; //asd/lol/aaaaa.txt
assertEquals("longer filename in other folder", expected, StringUtils.longestFilesystemPath(input));
}
@Test
public void sample() {
input = "dir\n\tsubdir1\n\tsubdir2\n\t\tfile.ext";
expected = 20; //dir/subdir2/file.ext
assertEquals("dir/subdir2/file.ext", expected, StringUtils.longestFilesystemPath(input));
input = "dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext";
expected = 32; //dir/subdir2/subsubdir2/file2.ext
assertEquals("dir/subdir2/subsubdir2/file2.ext", expected, StringUtils.longestFilesystemPath(input));
}
}
package com.blogspot.groglogs.test.stringutils;
import com.blogspot.groglogs.stringutils.StringUtils;
import org.junit.Test;
import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertNull;
public class LongestPalindromicSubstringJTests {
String input;
@Test
public void nullEmpty() {
input = null;
assertNull("null string", StringUtils.longestPalindromicSubstring(input));
input = "";
assertEquals("empty string", input, StringUtils.longestPalindromicSubstring(input));
}
@Test
public void oneCharacter() {
input = "a";
assertEquals("one character", input, StringUtils.longestPalindromicSubstring(input));
}
@Test
public void twoCharacters() {
input = "aa";
assertEquals("two characters palindrome", input, StringUtils.longestPalindromicSubstring(input));
input = "ab";
assertEquals("two characters not palindrome", "a", StringUtils.longestPalindromicSubstring(input));
}
@Test
public void threeCharacters() {
input = "aba";
assertEquals("three characters palindrome", input, StringUtils.longestPalindromicSubstring(input));
input = "abc";
assertEquals("three characters not palindrome", "a", StringUtils.longestPalindromicSubstring(input));
}
@Test
public void repeatedCharacters() {
input = "aaaa";
assertEquals("repeated same characters even length palindrome", input, StringUtils.longestPalindromicSubstring(input));
input = "abba";
assertEquals("repeated different characters even length palindrome", input, StringUtils.longestPalindromicSubstring(input));
input = "aaaaa";
assertEquals("repeated same characters odd length palindrome", input, StringUtils.longestPalindromicSubstring(input));
input = "abcba";
assertEquals("repeated all different characters odd length palindrome", input, StringUtils.longestPalindromicSubstring(input));
input = "abbba";
assertEquals("repeated different characters odd length palindrome", input, StringUtils.longestPalindromicSubstring(input));
}
@Test
public void sample() {
input = "banana";
assertEquals("banana", "anana", StringUtils.longestPalindromicSubstring(input));
input = "bananac";
assertEquals("bananac", "anana", StringUtils.longestPalindromicSubstring(input));
input = "bananab";
assertEquals("bananab", "bananab", StringUtils.longestPalindromicSubstring(input));
input = "million";
assertEquals("million", "illi", StringUtils.longestPalindromicSubstring(input));
input = "millio";
assertEquals("millio", "illi", StringUtils.longestPalindromicSubstring(input));
input = "ananabermkmkm";
assertEquals("multiple same length palindromes", "anana", StringUtils.longestPalindromicSubstring(input));
}
}
package com.blogspot.groglogs.test.stringutils;
import com.blogspot.groglogs.stringutils.StringUtils;
import org.junit.Test;
import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertNull;
public class LongestPalindromicSubstringManacherJTests {
String input;
@Test
public void nullEmpty() {
input = null;
assertNull("null string", StringUtils.longestPalindromicSubstringManacher(input));
input = "";
assertEquals("empty string", input, StringUtils.longestPalindromicSubstringManacher(input));
}
@Test
public void oneCharacter() {
input = "a";
assertEquals("one character", input, StringUtils.longestPalindromicSubstringManacher(input));
}
@Test
public void twoCharacters() {
input = "aa";
assertEquals("two characters palindrome", input, StringUtils.longestPalindromicSubstringManacher(input));
input = "ab";
assertEquals("two characters not palindrome", "a", StringUtils.longestPalindromicSubstringManacher(input));
}
@Test
public void threeCharacters() {
input = "aba";
assertEquals("three characters palindrome", input, StringUtils.longestPalindromicSubstringManacher(input));
input = "abc";
assertEquals("three characters not palindrome", "a", StringUtils.longestPalindromicSubstringManacher(input));
}
@Test
public void repeatedCharacters() {
input = "aaaa";
assertEquals("repeated same characters even length palindrome", input, StringUtils.longestPalindromicSubstringManacher(input));
input = "abba";
assertEquals("repeated different characters even length palindrome", input, StringUtils.longestPalindromicSubstringManacher(input));
input = "aaaaa";
assertEquals("repeated same characters odd length palindrome", input, StringUtils.longestPalindromicSubstringManacher(input));
input = "abcba";
assertEquals("repeated all different characters odd length palindrome", input, StringUtils.longestPalindromicSubstringManacher(input));
input = "abbba";
assertEquals("repeated different characters odd length palindrome", input, StringUtils.longestPalindromicSubstringManacher(input));
}
@Test
public void sample() {
input = "banana";
assertEquals("banana", "anana", StringUtils.longestPalindromicSubstringManacher(input));
input = "bananac";
assertEquals("bananac", "anana", StringUtils.longestPalindromicSubstringManacher(input));
input = "bananab";
assertEquals("bananab", "bananab", StringUtils.longestPalindromicSubstringManacher(input));
input = "million";
assertEquals("million", "illi", StringUtils.longestPalindromicSubstringManacher(input));
input = "millio";
assertEquals("millio", "illi", StringUtils.longestPalindromicSubstringManacher(input));
input = "ananabermkmkm";
assertEquals("multiple same length palindromes", "anana", StringUtils.longestPalindromicSubstringManacher(input));
}
}
package com.blogspot.groglogs.test.stringutils;
import com.blogspot.groglogs.stringutils.StringUtils;
import org.junit.Test;
import java.util.ArrayList;
import java.util.List;
import static org.junit.Assert.assertEquals;
public class LongestSubsequenceJTests {
String word, output, out;
List<String> words;
@Test
//null or empty
public void nullEmpty() {
word = null;
words = null;
try{
output = StringUtils.getLongestSubsequence(word, words);
} catch(IllegalArgumentException e){
System.out.println("Null word and list got IllegalArgumentException " + e.getMessage());
}
word = "asd";
words = new ArrayList<>();
try{
output = StringUtils.getLongestSubsequence(word, words);
} catch(IllegalArgumentException e){
System.out.println("Empty list got IllegalArgumentException " + e.getMessage());
}
}
@Test
public void notFound() {
word = "abppplee";
words = new ArrayList<>();
words.add("c");
words.add("cuda");
out = "";
output = StringUtils.getLongestSubsequence(word, words);
assertEquals("word not in list, expected empty", out, output);
word = "b";
words = new ArrayList<>();
words.add("c");
words.add("cuda");
out = "";
output = StringUtils.getLongestSubsequence(word, words);
assertEquals("word not in list, expected empty", out, output);
}
@Test
public void moreSameLength() {
word = "carbot";
words = new ArrayList<>();
words.add("car");
words.add("bot");
out = "car";
output = StringUtils.getLongestSubsequence(word, words);
assertEquals("more word same length in list, expected the first one", out, output);
}
@Test
public void extraChar() {
word = "carbot";
words = new ArrayList<>();
words.add("cara");
words.add("bota");
out = "";
output = StringUtils.getLongestSubsequence(word, words);
assertEquals("one extra char, expected empty", out, output);
}
@Test
public void random() {
word = "abppplee";
words = new ArrayList<>();
words.add("able");
words.add("ale");
words.add("apple");
words.add("bale");
words.add("kangaroo");
out = "apple";
output = StringUtils.getLongestSubsequence(word, words);
assertEquals("random string expected apple", out, output);
word = "abpppalleeoon";
words = new ArrayList<>();
words.add("able");
words.add("ale");
words.add("apple");
words.add("bale");
words.add("kangaroo");
words.add("balloon");
out = "balloon";
output = StringUtils.getLongestSubsequence(word, words);
assertEquals("random string expected balloon", out, output);
}
}
package com.blogspot.groglogs.test.stringutils;
import com.blogspot.groglogs.stringutils.StringUtils;
import org.junit.Test;
import static org.junit.Assert.assertEquals;
public class LongestSubstringWithKUniqueCharactersJTests {
String input, output;
int count;
@Test
public void nullEmpty() {
input = null;
count = 1;
assertEquals("null input", "", StringUtils.longestSubstringWithKUniqueCharacters(input, count));
input = "";
count = 1;
assertEquals("empty input", "", StringUtils.longestSubstringWithKUniqueCharacters(input, count));
input = "asd";
count = 0;
assertEquals("0 count", "", StringUtils.longestSubstringWithKUniqueCharacters(input, count));
input = "asd";
count = 23;
assertEquals("count more than string length", "", StringUtils.longestSubstringWithKUniqueCharacters(input, count));
}
@Test
public void badInput() {
input = "asd";
count = 23;
assertEquals("count more than string length", "", StringUtils.longestSubstringWithKUniqueCharacters(input, count));
}
@Test
public void sameCharacter() {
input = "aaa";
count = 1;
assertEquals("same character count 1", input, StringUtils.longestSubstringWithKUniqueCharacters(input, count));
input = "aaa";
count = 2;
assertEquals("same character count 2", "", StringUtils.longestSubstringWithKUniqueCharacters(input, count));
}
@Test
public void multipleCharacters() {
input = "abab";
count = 1;
output = "a";
assertEquals("multiple characters count 1", output, StringUtils.longestSubstringWithKUniqueCharacters(input, count));
input = "abab";
count = 2;
assertEquals("multiple charcaters count 2", input, StringUtils.longestSubstringWithKUniqueCharacters(input, count));
input = "abab";
count = 3;
assertEquals("multiple charcaters count 3", "", StringUtils.longestSubstringWithKUniqueCharacters(input, count));
}
@Test
public void sample() {
input = "abcba";
count = 2;
output = "bcb";
assertEquals("abcba count 2", output, StringUtils.longestSubstringWithKUniqueCharacters(input, count));
input = "abcde";
count = 3;
output = "abc";
assertEquals("abcde count 3", output, StringUtils.longestSubstringWithKUniqueCharacters(input, count));
input = "abcbaaaa";
count = 2;
output = "baaaa";
assertEquals("abcbaaaa count 2", output, StringUtils.longestSubstringWithKUniqueCharacters(input, count));
input = "bcbaaaa";
count = 2;
output = "baaaa";
assertEquals("bcbaaaa count 2", output, StringUtils.longestSubstringWithKUniqueCharacters(input, count));
}
}
package com.blogspot.groglogs.test.stringutils;
import com.blogspot.groglogs.stringutils.StringUtils;
import org.junit.Test;
import static org.junit.Assert.assertEquals;
public class LongestSubstringWithoutRepeatingCharactersJTests {
String input;
@Test
public void nullEmpty() {
input = null;
assertEquals("null string", 0, StringUtils.findLongestSubstringWithoutRepeatingCharacters(input));
input = "";
assertEquals("empty string", 0, StringUtils.findLongestSubstringWithoutRepeatingCharacters(input));
}
@Test
public void oneCharacter() {
input = "a";
assertEquals("one character string", 1, StringUtils.findLongestSubstringWithoutRepeatingCharacters(input));
}
@Test
public void allRepeatedCharacters() {
input = "aaaaaaaa";
assertEquals("all repeated characters string", 1, StringUtils.findLongestSubstringWithoutRepeatingCharacters(input));
}
@Test
public void repeatedCloseTogetherCharacters() {
input = "abcaade";
assertEquals("repeated characters close by string", 3, StringUtils.findLongestSubstringWithoutRepeatingCharacters(input));
input = "abcaabc";
assertEquals("repeated characters close by string", 3, StringUtils.findLongestSubstringWithoutRepeatingCharacters(input));
}
@Test
public void repeatedAtExtremes() {
input = "abcdefga";
assertEquals("repeated characters at extremes string", input.length() - 1, StringUtils.findLongestSubstringWithoutRepeatingCharacters(input));
}
@Test
public void allUniqueCharacters() {
input = "abcdefg";
assertEquals("all unique characters string", input.length(), StringUtils.findLongestSubstringWithoutRepeatingCharacters(input));
}
@Test
public void sampleString() {
input = "abrkaabcdefghijjxxx";
assertEquals("sample string", 10, StringUtils.findLongestSubstringWithoutRepeatingCharacters(input));
input = "abrkabcdefghijjxxx";
assertEquals("sample string", 12, StringUtils.findLongestSubstringWithoutRepeatingCharacters(input));
input = "abrkbcdefghijjxxx";
assertEquals("sample string", 11, StringUtils.findLongestSubstringWithoutRepeatingCharacters(input));
}
}
package com.blogspot.groglogs.test.stringutils;
import org.junit.Test;
import com.blogspot.groglogs.stringutils.StringUtils;
import static org.junit.Assert.assertEquals;
public class LookAndSayJTests {
int seed, input;
String output;
@Test
public void badInput() {
seed = 1;
input = 0;
try{
output = StringUtils.lookAndSay(seed, input);
}catch(IllegalArgumentException e){
System.out.println("Input 0 got IllegalArgumentException: " + e.getMessage());
}
seed = 1;
input = -1;
try{
output = StringUtils.lookAndSay(seed, input);
}catch(IllegalArgumentException e){
System.out.println("Input -1 got IllegalArgumentException: " + e.getMessage());
}
seed = 0;
input = 1;
try{
output = StringUtils.lookAndSay(seed, input);
}catch(IllegalArgumentException e){
System.out.println("Seed 0 got IllegalArgumentException: " + e.getMessage());
}
seed = -1;
input = 1;
try{
output = StringUtils.lookAndSay(seed, input);
}catch(IllegalArgumentException e){
System.out.println("Seed -1 got IllegalArgumentException: " + e.getMessage());
}
seed = -1;
input = -1;
try{
output = StringUtils.lookAndSay(seed, input);
}catch(IllegalArgumentException e){
System.out.println("Seed -1, input -1 got IllegalArgumentException: " + e.getMessage());
}
}
@Test
public void seed1() {
seed = 1;
input = 1;
output = "1";
assertEquals("1 expected 1", output, StringUtils.lookAndSay(seed, input));
input = 2;
output = "11";
assertEquals("2 expected 11", output, StringUtils.lookAndSay(seed, input));
input = 3;
output = "21";
assertEquals("3 expected 21", output, StringUtils.lookAndSay(seed, input));
input = 4;
output = "1211";
assertEquals("4 expected 1211", output, StringUtils.lookAndSay(seed, input));
input = 5;
output = "111221";
assertEquals("5 expected 111221", output, StringUtils.lookAndSay(seed, input));
input = 6;
output = "312211";
assertEquals("6 expected 312211", output, StringUtils.lookAndSay(seed, input));
input = 7;
output = "13112221";
assertEquals("7 expected 13112221", output, StringUtils.lookAndSay(seed, input));
input = 8;
output = "1113213211";
assertEquals("8 expected 1113213211", output, StringUtils.lookAndSay(seed, input));
input = 9;
output = "31131211131221";
assertEquals("9 expected 31131211131221", output, StringUtils.lookAndSay(seed, input));
}
@Test
public void seed2() {
seed = 2;
input = 1;
output = "2";
assertEquals("1 expected 2", output, StringUtils.lookAndSay(seed, input));
input = 2;
output = "12";
assertEquals("2 expected 12", output, StringUtils.lookAndSay(seed, input));
input = 3;
output = "1112";
assertEquals("3 expected 1112", output, StringUtils.lookAndSay(seed, input));
}
@Test
public void seed22() {
seed = 22;
input = 1;
output = "22";
assertEquals("1 expected 22", output, StringUtils.lookAndSay(seed, input));
input = 2;
output = "22";
assertEquals("2 expected 22", output, StringUtils.lookAndSay(seed, input));
input = 3;
output = "22";
assertEquals("3 expected 22", output, StringUtils.lookAndSay(seed, input));
}
}
package com.blogspot.groglogs.test.stringutils;
import org.junit.Test;
import com.blogspot.groglogs.stringutils.StringUtils;
import com.blogspot.groglogs.structures.*;
import static org.junit.Assert.assertEquals;
public class MaxRepCharJTests {
String input;
Entry output;
@Test
//null or empty expected null
public void nullEmpty() {
input = null;
output = null;
assertEquals("null string expected null", output, StringUtils.maxRepChar(input));
input = "";
assertEquals("empty string expected null", output, StringUtils.maxRepChar(input));
input = new String();
assertEquals("new string expected null", output, StringUtils.maxRepChar(input));
}
@Test
public void sameString() {
input = "aaaaa";
output = new Entry();
output.c = 'a';
output.count = 5;
assertEquals("aaaa string expected a,5", output, StringUtils.maxRepChar(input));
input = "t";
output = new Entry();
output.c = 't';
output.count = 1;
assertEquals("t string expected t,1", output, StringUtils.maxRepChar(input));
}
@Test
public void randomString() {
input = "gagggaatttt";
output = new Entry();
output.c = 't';
output.count = 4;
assertEquals("gagggaatttt string expected t,4", output, StringUtils.maxRepChar(input));
input = "some text!!!";
output = new Entry();
output.c = '!';
output.count = 3;
assertEquals("some text!!! string expected !,3", output, StringUtils.maxRepChar(input));
input = "asdfghjkl";
output = new Entry();
output.c = 'a';
output.count = 1;
assertEquals("asdfghjkl string expected a,1", output, StringUtils.maxRepChar(input));
}
}
package com.blogspot.groglogs.test.stringutils;
import com.blogspot.groglogs.stringutils.StringUtils;
import org.junit.Test;
import java.util.HashSet;
import java.util.Set;
import static org.junit.Assert.assertEquals;
public class MinDeletionsToFormDictionaryWordJTests {
String s;
Set<String> words;
int expected;
@Test
public void nullEmpty() {
s = null;
words = null;
expected = -1;
assertEquals("null input", expected, StringUtils.minDeletionsToFormDictionaryWord(s, words));
s = "";
words = new HashSet<>();
expected = -1;
assertEquals("empty input", expected, StringUtils.minDeletionsToFormDictionaryWord(s, words));
}
@Test
public void stringIsWord() {
s = "a";
words = new HashSet<>();
words.add("a");
expected = 0;
assertEquals("string is word", expected, StringUtils.minDeletionsToFormDictionaryWord(s, words));
}
@Test
public void noWordPossible() {
s = "a";
words = new HashSet<>();
words.add("lol");
expected = -1;
assertEquals("no word possible", expected, StringUtils.minDeletionsToFormDictionaryWord(s, words));
}
@Test
public void sample() {
s = "abca";
words = new HashSet<>();
words.add("a");
words.add("aa");
words.add("aaa");
expected = 2;
assertEquals("abca", expected, StringUtils.minDeletionsToFormDictionaryWord(s, words));
}
}
package com.blogspot.groglogs.test.stringutils;
import org.junit.Test;
import com.blogspot.groglogs.stringutils.StringUtils;
import static org.junit.Assert.assertEquals;
public class PalindromeJTests {
String input;
boolean output;
@Test
//null or empty input, expected false
public void nullEmpty() {
input = null;
output = false;
//null
assertEquals("null = null", output, StringUtils.isPalindrome(input));
input = new String();
//empty
assertEquals("empty = null", output, StringUtils.isPalindrome(input));
input = "";
//empty
assertEquals("empty = null", output, StringUtils.isPalindrome(input));
}
@Test
//not palindrome
public void notPalindrome() {
input = "MAN";
output = false;
assertEquals("MAN = false", output, StringUtils.isPalindrome(input));
input = "I am I";
output = false;
assertEquals("I am I = false", output, StringUtils.isPalindrome(input));
input = "I, 12, aM not";
output = false;
assertEquals("I, 12, aM not = false", output, StringUtils.isPalindrome(input));
}
@Test
//not palindrome
public void palindrome() {
input = "A";
output = true;
assertEquals("A = true", output, StringUtils.isPalindrome(input));
input = "MADAM";
output = true;
assertEquals("MADAM = true", output, StringUtils.isPalindrome(input));
input = "Poop";
output = true;
assertEquals("Poop = true", output, StringUtils.isPalindrome(input));
input = "PoOp";
output = true;
assertEquals("PoOp = true", output, StringUtils.isPalindrome(input));
input = "A man, a plan, a canal: Panama";
output = true;
assertEquals("A man, a plan, a canal: Panama = true", output, StringUtils.isPalindrome(input));
}
}
package com.blogspot.groglogs.test.stringutils;
import org.junit.Test;
import com.blogspot.groglogs.stringutils.StringUtils;
import java.util.HashSet;
import java.util.Set;
import static org.junit.Assert.assertEquals;
public class PermutateJTests {
String input;
Set<String> output, res;
@Test
//null or empty expected null
public void nullEmpty() {
input = null;
output = null;
assertEquals("null string expected null", output, StringUtils.getPermutations(input));
input = "";
assertEquals("empty string expected null", output, StringUtils.getPermutations(input));
input = new String();
assertEquals("new string expected null", output, StringUtils.getPermutations(input));
}
@Test
public void oneChar() {
input = "a";
output = new HashSet<>();
output.add(input);
res = StringUtils.getPermutations(input);
assertEquals("one character string expected same string", output, res);
assertEquals("multiple same character string expected same string once", 1, res.size());
}
@Test
public void moreSameChar() {
input = "aaa";
output = new HashSet<>();
output.add(input);
res = StringUtils.getPermutations(input);
assertEquals("multiple same character string expected same string", output, res);
assertEquals("multiple same character string expected same string once", 1, res.size());
}
@Test
public void randomNonRepeatingString() {
input = "car";
output = new HashSet<>();
output.add(input);
output.add("cra");
output.add("acr");
output.add("arc");
output.add("rca");
output.add("rac");
res = StringUtils.getPermutations(input);
assertEquals("random non repeating string", output, res);
assertEquals("random non repeating string length 3 expected 6 entries", 6, res.size());
}
@Test
public void randomRepeatingString() {
input = "caa";
output = new HashSet<>();
output.add(input);
output.add("aca");
output.add("aac");
res = StringUtils.getPermutations(input);
assertEquals("random repeating string", output, res);
assertEquals("random repeating string length 3 expected 3 entries", 3, res.size());
}
}
package com.blogspot.groglogs.test.stringutils;
import com.blogspot.groglogs.stringutils.StringUtils;
import org.junit.Test;
import static org.junit.Assert.assertEquals;
public class RegexJTests {
String input, regex;
@Test
//null or empty
public void nullEmpty() {
input = null;
regex = null;
assertEquals("null string and regex expected match", true, StringUtils.matchRegex(input, regex));
input = "";
regex = "";
assertEquals("empty string and regex expected match", true, StringUtils.matchRegex(input, regex));
input = new String();
regex = new String();
assertEquals("new string and new regex expected match", true, StringUtils.matchRegex(input, regex));
}
@Test
//only string or regex is null or empty
public void partialNullEmpty() {
input = null;
regex = "a";
assertEquals("null string and not null regex expected not match", false, StringUtils.matchRegex(input, regex));
input = "a";
regex = "";
assertEquals("not null string and empty regex expected match", true, StringUtils.matchRegex(input, regex));
}
@Test
//invalid regex, expected exception
public void invalidRegex() {
input = "a";
regex = "a$a"; //$ in the wrong place
boolean out;
int expected_errors = 0, gotten_errors = 0;
try{
expected_errors++;
out = StringUtils.matchRegex(input, regex);
} catch(IllegalArgumentException e){
gotten_errors++;
System.out.println("$ in the wrong place got IllegalArgumentException " + e.getMessage());
}
input = "a";
regex = "a^"; //^ in the wrong place
try{
expected_errors++;
out = StringUtils.matchRegex(input, regex);
} catch(IllegalArgumentException e){
gotten_errors++;
System.out.println("^ in the wrong place got IllegalArgumentException " + e.getMessage());
}
input = "a";
regex = "a["; //invalid character
try{
expected_errors++;
out = StringUtils.matchRegex(input, regex);
} catch(IllegalArgumentException e){
gotten_errors++;
System.out.println("invalid character [ got IllegalArgumentException " + e.getMessage());
}
input = "a";
regex = "*1"; //* in the wrong place
try{
expected_errors++;
out = StringUtils.matchRegex(input, regex);
} catch(IllegalArgumentException e){
gotten_errors++;
System.out.println("* in the wrong place got IllegalArgumentException " + e.getMessage());
}
input = "a";
regex = "^*"; //* does not follow . or alphanumeric character
try{
expected_errors++;
out = StringUtils.matchRegex(input, regex);
} catch(IllegalArgumentException e){
gotten_errors++;
System.out.println("* does not follow . or alphanumeric character got IllegalArgumentException " + e.getMessage());
}
assertEquals("Got as many errors as expected", expected_errors, gotten_errors);
}
@Test
public void matches() {
input = "a";
regex = "a";
assertEquals("a matches a", true, StringUtils.matchRegex(input, regex));
input = "aaa";
regex = "a*";
assertEquals("aaa matches a*", true, StringUtils.matchRegex(input, regex));
input = "aW9";
regex = "aW9";
assertEquals("aW9 matches aW9", true, StringUtils.matchRegex(input, regex));
input = "aW9bcW";
regex = "aW9";
assertEquals("aW9bcW matches aW9", true, StringUtils.matchRegex(input, regex));
input = "ab8aW9";
regex = "aW9";
assertEquals("ab8aW9 matches aW9", true, StringUtils.matchRegex(input, regex));
input = "cc2aW9raW9z";
regex = "aW9";
assertEquals("cc2aW9raW9z matches aW9", true, StringUtils.matchRegex(input, regex));
input = "ab9w";
regex = "a.9.";
assertEquals("ab9w matches a.9.", true, StringUtils.matchRegex(input, regex));
input = "ac9bcW";
regex = "a.9.";
assertEquals("ac9bcW matches a.9.", true, StringUtils.matchRegex(input, regex));
input = "ab8a999";
regex = "a.9.";
assertEquals("ab8a999 matches a.9.", true, StringUtils.matchRegex(input, regex));
input = "cc2aW9r";
regex = "a.9.";
assertEquals("cc2aW9r matches a.9.", true, StringUtils.matchRegex(input, regex));
input = "a9";
regex = "aW*9";
assertEquals("a9 matches aW*9", true, StringUtils.matchRegex(input, regex));
input = "aW9";
regex = "aW*9";
assertEquals("aW9 matches aW*9", true, StringUtils.matchRegex(input, regex));
input = "aWW9b9cW";
regex = "aW*9";
assertEquals("aWW9b9cW matches aW*9", true, StringUtils.matchRegex(input, regex));
input = "aU9aWW9";
regex = "aW*9";
assertEquals("aU9aWW9 matches aW*9", true, StringUtils.matchRegex(input, regex));
input = "ab8aWWW9W9aa";
regex = "aW*9";
assertEquals("ab8aWWW9W9aa matches aW*9", true, StringUtils.matchRegex(input, regex));
input = "cc2a9raW9zWW9ac";
regex = "aW*9";
assertEquals("cc2a9raW9zWW9ac matches aW*9", true, StringUtils.matchRegex(input, regex));
input = "a9";
regex = "a.*9";
assertEquals("a9 matches a.*9", true, StringUtils.matchRegex(input, regex));
input = "aZ9";
regex = "a.*9";
assertEquals("aZ9 matches a.*9", true, StringUtils.matchRegex(input, regex));
input = "aZW9b9cW";
regex = "a.*9";
assertEquals("aZW9b9cW matches a.*9", true, StringUtils.matchRegex(input, regex));
input = "aU9a9";
regex = "a.*9";
assertEquals("aU9a9 matches a.*9", true, StringUtils.matchRegex(input, regex));
input = "b8aWUW9W";
regex = "a.*9";
assertEquals("b8aWUW9W matches a.*9", true, StringUtils.matchRegex(input, regex));
input = "cc2a9raU9z";
regex = "a.*9";
assertEquals("cc2a9raU9z matches a.*9", true, StringUtils.matchRegex(input, regex));
input = "ceaW999zb34b3az";
regex = "aW9*.b3";
assertEquals("ceaW999zb34b3az matches aW9*.b3", true, StringUtils.matchRegex(input, regex));
input = "ceaW9b34";
regex = "aW9*.b3";
assertEquals("ceaW9b34 matches aW9*.b3", true, StringUtils.matchRegex(input, regex));
input = "pqaWzb38q";
regex = "aW9*.b3";
assertEquals("pqaWzb38q matches aW9*.b3", true, StringUtils.matchRegex(input, regex));
input = "aW99zer";
regex = "^aW.9";
assertEquals("aW99zer matches ^aW.9", true, StringUtils.matchRegex(input, regex));
input = "aWW9";
regex = "^aW.9";
assertEquals("aWW9 matches ^aW.9", true, StringUtils.matchRegex(input, regex));
input = "aWP9GA";
regex = "^aW.9";
assertEquals("aWP9GA matches ^aW.9", true, StringUtils.matchRegex(input, regex));
input = "aWW9";
regex = "aW.9$";
assertEquals("aWW9 matches aW.9$", true, StringUtils.matchRegex(input, regex));
input = "aWW9abcaWz9";
regex = "aW.9$";
assertEquals("aWW9abcaWz9 matches aW.9$", true, StringUtils.matchRegex(input, regex));
input = "baaWX9";
regex = "aW.9$";
assertEquals("baaWX9 matches aW.9$", true, StringUtils.matchRegex(input, regex));
input = "abcaWP9";
regex = "aW.9$";
assertEquals("abcaWP9 matches aW.9$", true, StringUtils.matchRegex(input, regex));
input = "aW9";
regex = "^aW9$";
assertEquals("aW9 matches ^aW9$", true, StringUtils.matchRegex(input, regex));
}
@Test
public void notMatches() {
input = "a";
regex = "b";
assertEquals("a not matches b", false, StringUtils.matchRegex(input, regex));
input = "aaa";
regex = "a*b";
assertEquals("aaa not matches a*b", false, StringUtils.matchRegex(input, regex));
input = "aW8";
regex = "aW9";
assertEquals("aW8 not matches aW9", false, StringUtils.matchRegex(input, regex));
input = "bcd8";
regex = "aW9";
assertEquals("bcd8 not matches aW9", false, StringUtils.matchRegex(input, regex));
input = "az9";
regex = "a.9.";
assertEquals("az9 not matches a.9.", false, StringUtils.matchRegex(input, regex));
input = "a989a";
regex = "a.9.";
assertEquals("a989a not matches a.9.", false, StringUtils.matchRegex(input, regex));
input = "bac9";
regex = "a.9.";
assertEquals("bac9 not matches a.9.", false, StringUtils.matchRegex(input, regex));
input = "aWWU9";
regex = "aW*9";
assertEquals("aWWU9 not matches aW*9", false, StringUtils.matchRegex(input, regex));
input = "baX9";
regex = "aW*9";
assertEquals("baX9 not matches aW*9", false, StringUtils.matchRegex(input, regex));
input = "aXW9Wa";
regex = "aW*9";
assertEquals("aXW9Wa not matches aW*9", false, StringUtils.matchRegex(input, regex));
input = "9UWaW8";
regex = "a.*9";
assertEquals("9UWaW8 not matches a.*9", false, StringUtils.matchRegex(input, regex));
input = "b9aaaX";
regex = "a.*9";
assertEquals("b9aaaX not matches a.*9", false, StringUtils.matchRegex(input, regex));
input = "XUq8";
regex = "a.*9";
assertEquals("XUq8 not matches a.*9", false, StringUtils.matchRegex(input, regex));
input = "ceaW98zb34";
regex = "aW9*.b3";
assertEquals("ceaW98zb34 not matches aW9*.b3", false, StringUtils.matchRegex(input, regex));
input = "pqaW988b38q";
regex = "aW9*.b3";
assertEquals("pqaW988b38q not matches aW9*.b3", false, StringUtils.matchRegex(input, regex));
input = "baWx9";
regex = "^aW.9";
assertEquals("baWx9 not matches ^aW.9", false, StringUtils.matchRegex(input, regex));
input = "aW9";
regex = "^aW.9";
assertEquals("aW9 not matches ^aW.9", false, StringUtils.matchRegex(input, regex));
input = "aWcc90";
regex = "^aW.9";
assertEquals("aWcc90 not matches ^aW.9", false, StringUtils.matchRegex(input, regex));
input = "aWW99";
regex = "aW.9$";
assertEquals("aWW99 not matches aW.9$", false, StringUtils.matchRegex(input, regex));
input = "aW";
regex = "aW.9$";
assertEquals("aW not matches aW.9$", false, StringUtils.matchRegex(input, regex));
input = "aWcc90";
regex = "aW.9$";
assertEquals("aWcc90 not matches aW.9$", false, StringUtils.matchRegex(input, regex));
input = "aaW9";
regex = "^aW9$";
assertEquals("aaW9 not matches ^aW9$", false, StringUtils.matchRegex(input, regex));
input = "aW9aW9";
regex = "^aW9$";
assertEquals("aW9aW9 not matches ^aW9$", false, StringUtils.matchRegex(input, regex));
input = "aW99";
regex = "^aW9$";
assertEquals("aW99 not matches ^aW9$", false, StringUtils.matchRegex(input, regex));
}
}
package com.blogspot.groglogs.test.stringutils;
import org.junit.Test;
import com.blogspot.groglogs.stringutils.StringUtils;
import static org.junit.Assert.assertEquals;
public class ReplaceSpaceJTests {
String input, output;
@Test
//null or empty expected null
public void nullEmpty() {
input = null;
output = null;
assertEquals("null string expected null", output, StringUtils.replaceSpace(input));
input = "";
assertEquals("empty string expected null", output, StringUtils.replaceSpace(input));
input = new String();
assertEquals("new string expected null", output, StringUtils.replaceSpace(input));
}
@Test
public void noSpace() {
input = "aaaaa";
output = "aaaaa";
assertEquals("aaaa string expected aaaaa", output, StringUtils.replaceSpace(input));
input = "t!";
output = "t!";
assertEquals("t! string expected t!", output, StringUtils.replaceSpace(input));
}
@Test
public void withSpace() {
input = "ga ggg aatttt";
output = "ga%20ggg%20aatttt";
assertEquals("ga ggg aatttt string expected ga%20ggg%20aatttt", output, StringUtils.replaceSpace(input));
input = " ";
output = "%20%20%20";
assertEquals(" string expected %20%20%20", output, StringUtils.replaceSpace(input));
input = "Some long string with little sense and lots of spaces";
output = "Some%20long%20string%20with%20little%20sense%20and%20lots%20of%20spaces";
assertEquals("Some long string with little sense and lots of spaces string expected Some%20long%20string%20with%20little%20sense%20and%20lots%20of%20spaces", output, StringUtils.replaceSpace(input));
}
}
package com.blogspot.groglogs.test.stringutils;
import com.blogspot.groglogs.stringutils.StringUtils;
import org.junit.Test;
import static org.junit.Assert.assertEquals;
public class SimplifyPathJTests {
String s, expected;
@Test
public void nullEmpty() {
s = null;
assertEquals("null", s, StringUtils.simplifyPath(s));
s = "";
assertEquals("empty", s, StringUtils.simplifyPath(s));
}
@Test
public void dots() {
s = ".";
expected = "/";
assertEquals(".", expected, StringUtils.simplifyPath(s));
s = "/.";
expected = "/";
assertEquals("/.", expected, StringUtils.simplifyPath(s));
s = "/./";
expected = "/";
assertEquals("/./", expected, StringUtils.simplifyPath(s));
s = "..";
expected = "/";
assertEquals("..", expected, StringUtils.simplifyPath(s));
s = "/..";
expected = "/";
assertEquals("/..", expected, StringUtils.simplifyPath(s));
s = "/../";
expected = "/";
assertEquals("/../", expected, StringUtils.simplifyPath(s));
s = ".hidden";
expected = "/.hidden";
assertEquals(".hidden", expected, StringUtils.simplifyPath(s));
s = "..hidden";
expected = "/..hidden";
assertEquals("..hidden", expected, StringUtils.simplifyPath(s));
s = "...hidden";
expected = "/...hidden";
assertEquals("...hidden", expected, StringUtils.simplifyPath(s));
}
@Test
public void sample() {
s = "/home/";
expected = "/home";
assertEquals("/home/", expected, StringUtils.simplifyPath(s));
s = "/home//foo/";
expected = "/home/foo";
assertEquals("home//foo/", expected, StringUtils.simplifyPath(s));
s = "/a/./b/../../c/";
expected = "/c";
assertEquals("/a/./b/../../c/", expected, StringUtils.simplifyPath(s));
}
}
package com.blogspot.groglogs.stringutils;
import com.blogspot.groglogs.structures.Entry;
import com.blogspot.groglogs.structures.Pair;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
import java.util.Set;
import java.util.List;
import java.util.HashSet;
import java.util.Stack;
public class StringUtils {
public static final char REGEX_MATCH_ANY = '.';
public static final char REGEX_MATCH_MANY = '*';
public static final char REGEX_MATCH_AT_START = '^';
public static final char REGEX_MATCH_AT_END = '$';
//used for Manacher's algorithm
public static final char MANACHER_START_STRING = '^';
public static final char MANACHER_END_STRING = '$';
public static final char MANACHER_CHAR_SEP = '#';
public static boolean isPalindrome(String s){
if(s == null || s.length() < 1)return false;
for(int i = 0, j = s.length() - 1; j > i; ){
if(!Character.isLetterOrDigit(s.charAt(i))){
i++;
continue;
}
if(!Character.isLetterOrDigit(s.charAt(j))){
j--;
continue;
}
if(Character.toLowerCase(s.charAt(i)) != Character.toLowerCase(s.charAt(j)))return false;
else{
i++;
j--;
}
}
return true;
}
public static String stringCompress(String s){
if(s == null || s.length() <= 1) return s;
int[] counts = new int[s.length()];
char[] chars = new char[s.length()];
char c;
int j = 0;
counts[0] = 1;
chars[0] = s.charAt(0);
//for each character in string, count how many times it appears
for(int i = 1; i < s.length(); i++){
c = s.charAt(i);
if(c == chars[j]) counts[j]++;
else{
j++;
chars[j] = c;
counts[j] = 1;
}
}
//if we compressed the string a bit, then our arrays have some space left, mark the premature end
if(j < counts.length - 1) counts[++j] = -1;
//we do not want to create a new String everytime while we concatenate
StringBuilder sb = new StringBuilder();
j = 0;
while(j < counts.length){
if(counts[j] == -1) break;
//for each character in original string, concatenate it alongside the number of occurrences
sb.append(chars[j]);
sb.append(counts[j]);
j++;
}
//if the compressed string is longer, return original string instead
if(sb.length() > s.length()) return s;
return sb.toString();
}
public static String replaceSpace(String s){
if(s == null || s.length() == 0) return null;
int space_count = 0;
char c;
//count how many white spaces we have
for(int i = 0; i < s.length(); i++){
c = s.charAt(i);
if(c == ' ') space_count++;
}
if(space_count == 0) return s;
//allocate space for new string replacement. CAREFUL: we replace 1 char with 3 so we need 2 extra spaces!
char[] res = new char[s.length() + space_count * 2];
//prepare result string. CAREFUL: can't use same index otherwise we skip characters in either string or char[]
for(int i = 0, j = 0; j < s.length(); i++, j++){
c = s.charAt(j);
if(c == ' '){
res[i] = '%';
res[++i] = '2';
res[++i] = '0';
}
else res[i] = c;
}
return new String(res);
}
public static Entry maxRepChar(String s){
Entry max = new Entry(), curr = new Entry();
char c;
if(s == null || s.length() == 0) return null;
//initialize with first item in string
curr.count = 0;
curr.c = s.charAt(0);
max.count = 0;
for(int i = 0; i < s.length(); i++){
c = s.charAt(i);
/*
keep incrementing the current counter for the item we're evaluating now
as long as we have a subsequent uninterrupted stream
*/
if(c == curr.c) curr.count++;
else{
/*
when we interrupt the stream, check if the item we're evaluating
appeared more times than the current maximum, if so, set it as max
*/
if(curr.count > max.count){
max.count = curr.count;
max.c = curr.c;
}
//and reset the counter for current item
curr.c = c;
curr.count = 1;
}
}
//don't miss the case when the max run until end of string
if(curr.count > max.count){
max.count = curr.count;
max.c = curr.c;
}
return max;
}
/*
The look and say sequence is generated by starting with a seed number
then looking at the digits of the number and describing how many of each consecutive ones there are
Eg with seed 1:
1 -> one 1
11 -> two 1
21 -> one 2, one 1
To get the nth in the sequence, we generate all of them :(
*/
public static String lookAndSay(int seed, int n){
if(seed <= 0) throw new IllegalArgumentException("Seed must be greater than 0: " + seed);
if(n <= 0) throw new IllegalArgumentException("Input must be greater than 0: " + n);
//we collect here the final and intermediate outputs
String res = "" + seed;
StringBuilder sb;
char c;
int i = 1, curr_count;
while(i < n){
sb = new StringBuilder();
c = res.charAt(0);
curr_count = 1;
//pick the first character in the partial output and start counting how many times does it appear
for(int j = 1; j < res.length(); j++){
if(res.charAt(j) == c) curr_count++;
//as soon as we encounter a different character, update the result and reset the counter
else{
sb.append(String.valueOf(curr_count) + c);
c = res.charAt(j);
curr_count = 1;
}
}
i++;
//do not forget the last append!
sb.append(String.valueOf(curr_count) + c);
//update the partial output
res = sb.toString();
}
return res;
}
//Generate all permutations for a given string, skipping duplicates. Recursive implementation
private static void permutate(int size, StringBuilder curr, StringBuilder left, Set<String> out){
StringBuilder sb = new StringBuilder(curr);
//if we built the full string, add it to the result and return
if(left.length() == 0){
//we might not have any more characters left to choose from, but the string can still be incomplete!
if(sb.length() == size) out.add(sb.toString());
return;
}
//foreach remaining character, add it to the current string, then recurse on the remaining ones leaving that out
for(int i = left.length() - 1; i >= 0; i--){
StringBuilder next = new StringBuilder(curr);
next.append(left.charAt(i));
//deleteCharAt if used on left itself will alter it permanently and not return a new object!
StringBuilder rest = new StringBuilder(left).deleteCharAt(i);
permutate(size, next, rest, out);
}
}
public static Set<String> getPermutations(String s){
if(s == null || s.isEmpty()) return null;
Set<String> permutations = new HashSet<>();
permutate(s.length(), new StringBuilder(), new StringBuilder(s), permutations);
return permutations;
}
/*
Given a string and a list of words, find the longest word that can be created from the input string
by only skipping characters from it
*/
public static String getLongestSubsequence(String s, List<String> words){
if(s == null || words == null || s.isEmpty() || words.isEmpty()) throw new IllegalArgumentException("Input string and word list cannot be null or empty!");
//key is the next character we need to find to move further in a word
//value is a map (could also be a list of tuples) of words we are building up for which that is the next character we need
//with the indication of the length matched so far. If we ever build the full word, we check it and track it as longest in case
//then keep iterating until the String has been parsed entirely
HashMap<Character, Map<String, Integer>> nextCharsForWord = new HashMap<>();
String currLongest = "";
//prepare structure
for(String word : words){
Character c = word.charAt(0);
//get map, create one if no entry exists yet
Map<String, Integer> m = nextCharsForWord.get(c);
if(m == null) m = new HashMap<>();
//add word to map and put it in next character map
m.put(word, 0);
nextCharsForWord.put(c, m);
}
//loop over each character in input string and match, if possible, with the known next required characters from the value map
//for every match, reorganise the map so that the word is tracked in the value map corresponding to the next character we need
for(Character c: s.toCharArray()){
//get words that need this character next
Map<String, Integer> m = nextCharsForWord.get(c);
//no work for non required characters
if(m != null){
//check each word that need this character
Iterator<Map.Entry<String, Integer>> iter = m.entrySet().iterator();
while(iter.hasNext()) {
Map.Entry<String, Integer> e = iter.next();
String word = e.getKey();
Integer len = e.getValue();
//if word is complete, remove it from the search and track if it's the longest so far
if (word.length() == len + 1) {
iter.remove();
if(word.length() > currLongest.length()) currLongest = word;
continue;
}
//otherwise increment found counter for it and place it in the value map for the search of the next character
Character nextChar = e.getKey().charAt(e.getValue() + 1);
Map<String, Integer> nextWords = nextCharsForWord.get(nextChar);
if(nextWords == null) nextWords = new HashMap<>();
nextWords.put(word, len + 1);
nextCharsForWord.put(nextChar, nextWords);
}
}
}
return currLongest;
}
/*
Given a string in the format k[content], convert it to a string made of k repetitions of content
this can be nested
0 means empty string
no k means 1
*/
public static String decompress(String s){
if(s == null || s.isEmpty()) throw new IllegalArgumentException("String cannot be empty or null!");
//we will keep track of the parsing and elaboration progress in a stack
Stack<String> parsed = new Stack<>();
StringBuilder curr = new StringBuilder();
//start building up the stack for each character in the string
for(int i = 0; i < s.length(); i++){
char c = s.charAt(i);
switch (c){
case '[':
//maybe we just found a number, push it to the stack
String rep = curr.toString();
//or maybe it was null, therefore assume 1 repetition
if(rep.length() == 0) rep = "1";
parsed.push(rep);
parsed.push("["); //we will use this marker to match against the respective close parenthesis
curr = new StringBuilder();
break;
case ']':
//process the current expression - everything we have so far until the matching open parenthesis
String tmp = curr.toString();
curr = new StringBuilder();
curr.append(tmp);
//reverse append until we find the start bracket
//this is because we are walking the stack top to bottom
//every new element actually comes before us
while(parsed.peek() != "["){
curr.insert(0, parsed.pop());
}
parsed.pop();//get rid of bracket
//find the number of repetitions we need to perform
int repetitions = Integer.parseInt(parsed.pop());
//if we have to, repeat the string
if(repetitions != 0) {
tmp = curr.toString();
curr = new StringBuilder();
for (int j = 0; j < repetitions; j++) {
curr.append(tmp);
}
parsed.push(curr.toString());
}
else parsed.push(""); //otherwise throw everything away
curr = new StringBuilder();
break;
default:
curr. append(c);
}
}
//when we reach the end of the string, we might still have pieces on the stack to assemble
//keep the last string piece we read so far (will be the last piece of the final string)
String tmp = curr.toString();
curr = new StringBuilder();
curr.append(tmp);
//prepend all the other pieces, if any, we calculated to create the result string
while(!parsed.empty()){
curr.insert(0, parsed.pop());
}
return curr.toString();
}
//helper for matchRegex
private static boolean isMatch(String s, String regex){
//we finished the matching without returning false, before so we matched all
if(regex == null || regex.length() == 0) return true;
//invalid regex, ^ is not at the beginning (checked before) or * is found without a preceding . or alphanumeric character
if(regex.charAt(0) == REGEX_MATCH_AT_START) throw new IllegalArgumentException("Invalid regex, " + REGEX_MATCH_AT_START + " not found at the beginning!");
if(regex.charAt(0) == REGEX_MATCH_MANY) throw new IllegalArgumentException("Invalid regex, " + REGEX_MATCH_MANY + " not preceded by " + REGEX_MATCH_ANY + " or alphanumeric character!");
//check if we were asked to match at the end with $, it means the string has to be fully consumed by now
//otherwise we matched the whole string but are not at the ned
if(regex.charAt(0) == REGEX_MATCH_AT_END){
//invalid regex, $ is not at the end
if(regex.length() != 1) throw new IllegalArgumentException("Invalid regex, $ found before the end!");
return s.length() == 0;
}
//check if we have a * now, means must match whatever alphanumeric character before it (or any if it's a .)
//could also match 0 instances of it. In both cases we need to keep processing the rest of the regex
//at SOME point afterwards
if(regex.length() > 1 && regex.charAt(1) == REGEX_MATCH_MANY){
//see if we can match 1+ instances of the character
char match = regex.charAt(0);
//for any valid match of the *, check if the rest of the string already matches the rest of the regex
//CAUTION! the condition on match MUST be in the cycle conditions and NOT inside
//since we want to proceed only as long as we can keep matching the char before the *
for(int i = 0; i < s.length() && (match == REGEX_MATCH_ANY || match == s.charAt(i)); i++){
if(isMatch(s.substring(i + 1), regex.substring(2))) return true;
}
//if we had 0 matches from the *, which is allowed, check if the rest of the string matches the rest of the regex
return isMatch(s, regex.substring(2));
}
//only thing left is an alphanumeric or . character at the beginning of the regex
//any other character is an exception
if(!(regex.charAt(0) == REGEX_MATCH_ANY) && !Character.isLetterOrDigit(regex.charAt(0))) throw new IllegalArgumentException("Invalid regex, expected alphanumeric character or " + REGEX_MATCH_ANY + " but found: " + regex.charAt(0));
//if we still have matches to perform but the string is finished, we can't match the regex
if(s.length() == 0) return false;
//if we have a . or a character, check if the character matches the expected one and moe on to the next match
if(regex.charAt(0) == REGEX_MATCH_ANY || regex.charAt(0) == s.charAt(0)) return isMatch(s.substring(1), regex.substring(1));
//character match failed, expression cannot be matched
return false;
}
/*
Following syntax is allowed
alphanumeric - matches exactly that character
. - matches any character
* - must follow . or an alphanumeric character, means we can match multiple instances of the preceding character
^ - must be the first character, means the matching has to begin from the start
$ - must be the last character, means the matching has to occur at the end
in the absence of ^ and $, the match can occur anywhere in the string
*/
public static boolean matchRegex(String s, String regex){
//empty string is only matched my empty regex
if((s == null || s.length() == 0) && (regex != null && regex.length() > 0)) return false;
//empty regex matches all strings
if(regex == null || regex.length() == 0) return true;
//check if we need to match from the beginning
if(regex.charAt(0) == REGEX_MATCH_AT_START) return isMatch(s, regex.substring(1));
//else we need to evaluate the matching starting at every place
for(int i = 0; i < s.length(); i++) {
if(isMatch(s.substring(i), regex)) return true;
}
//whole string processed, no match found
return false;
}
/*
A string is the result of interleaving two other strings if it contains ALL character from both strings in the same order
as they appear in the sources. You can pick at each time 0+ characters from either string!
Eg:
ABACCA is the interleaving of ABC and ACA -> AB, A, C, CA
ABACAC is also the interleaving of ABC and ACA -> AB, AC, A, C
ABAACC is NOT the interleaving of ABC and ACA -> AB, A, we expect now a C but find an A instead
*/
//version with no DP structure
public static boolean findInterleaveNoDP(String a, String b, String c){
//all null or empty strings are interleaved
if(c == null || c.isEmpty()) return (a == null || a.isEmpty()) && (b == null || b.isEmpty());
//if one string is null, other two must match
if(a == null || a.isEmpty()) return c.equals(b);
if(b == null || b.isEmpty()) return c.equals(a);
//if length does not add up, for sure no interleave
if(c.length() != a.length() + b.length()) return false;
boolean a_match = false, b_match = false;
//since we can get 0+ characters from either string, explore both possibilities if any of the two matches the current
//character in the result. If there is no match, since order is important, for sure we eliminate that branch
//the two strings can match in multiple ways as well, we just need to find one
if(c.charAt(0) == a.charAt(0)){
a_match = findInterleaveNoDP((a.length() > 1) ? a.substring(1) : null, b, (c.length() > 1) ? c.substring(1) : null);
}
//no need to continue if we found a match already
if(a_match) return true;
if(c.charAt(0) == b.charAt(0)){
b_match = findInterleaveNoDP(a, (b.length() > 1) ? b.substring(1) : null, (c.length() > 1) ? c.substring(1) : null);
}
return b_match;
}
//helper for isInterleave
private static boolean findInterleave(String a, String b, String c, int a_idx, int b_idx, Boolean[][] a_matches, Boolean[][] b_matches){
//if one string is null, other two must match, this is our base case
if(a == null) return c.equals(b);
if(b == null) return c.equals(a);
boolean a_match = false, b_match = false;
//if we already have calculated this scenario, get the value from the cache
//otherwise compute it and store it for later. Do this for both strings due to the 0+ matching condition
//but if we have a lot of overlapping we can recycle work already done
if(a_matches[a_idx][b_idx] != null){
a_match = a_matches[a_idx][b_idx];
} else if(c.charAt(0) == a.charAt(0)){
//if they do not match we have initialized to false anyway
//avoid index out of range by checking first before the substring operation
//advance the index for each string alternatively. It is only used for checking the cache
a_match = findInterleave((a.length() > 1) ? a.substring(1) : null, b, (c.length() > 1) ? c.substring(1) : null, a_idx + 1, b_idx, a_matches, b_matches);
}
a_matches[a_idx][b_idx] = a_match;
//no need to continue if we found a match already
if(a_match) return true;
if(b_matches[b_idx][a_idx] != null){
b_match = b_matches[b_idx][a_idx];
} else if(c.charAt(0) == b.charAt(0)){
b_match = findInterleave(a, (b.length() > 1) ? b.substring(1) : null, (c.length() > 1) ? c.substring(1) : null, a_idx, b_idx + 1, a_matches, b_matches);
}
b_matches[b_idx][a_idx] = b_match;
return b_match;
}
public static boolean isInterleave(String a, String b, String c) {
//all null or empty strings are interleaved
if(c == null || c.isEmpty()) return (a == null || a.isEmpty()) && (b == null || b.isEmpty());
//if one string is null, other two must match
//we will repeat this as base case in the inner function too
//it's here so that we skip other operations if this situation appears immediately
if(a == null || a.isEmpty()) return c.equals(b);
if(b == null || b.isEmpty()) return c.equals(a);
//if length does not add up, for sure no interleave
if(c.length() != a.length() + b.length()) return false;
//keep two structures where we mark for each index in each string if we found a match from that combination
//for both strings, so that when we process them later we recycle work already done
//this is useful when the two strings overlap in many places
Boolean[][] a_matches = new Boolean[a.length()][b.length()];
Boolean[][] b_matches = new Boolean[b.length()][a.length()];
return findInterleave(a, b, c, 0, 0, a_matches, b_matches);
}
/**
* Given a string with potentially repeating characters, find the maximum length of the substring without repeated characters.
* @param s the given string.
* @return the maximum length of the substring without repeated characters.
*/
public static int findLongestSubstringWithoutRepeatingCharacters(String s){
if(s == null || s.length() == 0){
return 0;
}
/*
We can track for each character the last position we encountered it and use a sliding window technique
with two pointers starting at the beginning of the string and having one pointer always move forward
while the other pointer jumps forward based on where are we currently and where was the repeated character last seen.
While moving, we also verify whether we have found a repetition or not,
then calculate the length of the current substring and update the maximum if necessary.
If we find a repetition, our window extremes are in one of three possible cases and we need to determine how to shrink it.
Between the repetitions there can be any number of characters, even 0.
(1) FIRST time we encounter a repeated character:
i j
A...A...
we increment i to reduce our window range and exclude the first occurrence of the
repeated character, we want to keep investigating the longest substring without it
This means for string abca, we'd say the longest substring is 3: bca and NOT 3: abc, this is VERY important
as trying to include that very first character in our logic will break for example if the first occurrence
of the repeated character is exactly in position 0 as it requires special handling.
In terms of logic for LENGTH, the result is the same however.
(2) we have already seen this repeated character AFTER our window start position (i)
i j
AB...AA...
we jump i to the position AFTER the last position we encountered for the repeated character (in this case move i to j),
since no substring in our window will be longer that the previous ones we analyzed
and each substring from i to any new j will contain the same repetition and therefore be invalid.
(3) we have already seen this repeated character BEFORE our window start position (i)
ij
AB...AAB...
we IGNORE this, since it is BEFORE our window start, therefore already outside of our search range
Lastly, in ALL cases, we ALWAYS update the last position we encountered a certain character
*/
int max = 0;
Map<Character, Integer> characterSeenAt = new HashMap<>();
for(int i = 0, j = 0; i < s.length() && j < s.length(); j++){
char c = s.charAt(j);
int lastSeenAt = characterSeenAt.getOrDefault(c, -1);
//if we have seen this character already AND its position is NOT before i (our window start range)
//move i AFTER the last seen position for it
//if this was the FIRST time we saw the repeated character, i will move one step right
//otherwise i will jump to the position AFTER the LATEST position we encountered for this repeated character
if(lastSeenAt >= i){
i = lastSeenAt + 1;
}
//always check if we have found a longer valid substring and update our result as necessary
int count = j - i + 1;
if(count > max){
max = count;
}
//track where did we see this character last
//important to do this AFTER the rest of the logic, otherwise we won't correctly reposition the
//start of our range
characterSeenAt.put(c, j);
}
return max;
}
//helper for longestPalindromicSubstring
//given a string and a pair or indices, move outwards until the string is no longer a palindrome
//in the input bounds we set the lower and upper index for the found palindrome and return the total length in output
private static int checkPalindrome(String s, Pair<Integer, Integer> bounds){
int start = bounds.getFirst(), end = bounds.getSecond();
int length = end - start;
while(start >= 0 && end < s.length()){
if(s.charAt(start) != s.charAt(end)){
break;
}
length++;
start--;
end++;
}
//if we stopped, we have found two characters that are not same or fell off the string boundaries
//the actual start and end are the values BEFORE we stopped
bounds.setFirst(start + 1);
bounds.setSecond(end - 1);
return length;
}
/**
* Given a string, find the longest palindromic substring.
* @param s the given string.
* @return the longest palindromic substring in this string. If there are multiple ones, return the first one.
*/
public static String longestPalindromicSubstring(String s){
if(s == null || s.length() <= 1){
return s;
}
//initially the longest palindromic substring is a single character, pick the first one
int maxLength = 1, maxStart = 0, maxEnd = 0;
//for each character and space between characters in the string, check if it could be a valid center of a palindrome
//first character is already considered, so skip it
for(int i = 1; i < s.length(); i++){
int currMaxLength;
//first loop, check odd length palindromes, center is on a character in the string
//for each character in the string, we expand outwards and check whether we have a palindrome
Pair<Integer, Integer> bounds = new Pair<>(i, i);
currMaxLength = checkPalindrome(s, bounds);
if(currMaxLength > maxLength){
maxLength = currMaxLength;
maxStart = bounds.getFirst();
maxEnd = bounds.getSecond();
}
//second loop, check even length palindromes, center is between two characters in the string
//for each place in between characters in the string, we expand outwards and check whether we have a palindrome
//i - 1, i since we start the loop from the second character in the string, so lower bound is before the current character
bounds = new Pair<>(i - 1, i);
currMaxLength = checkPalindrome(s, bounds);
if(currMaxLength > maxLength){
maxLength = currMaxLength;
maxStart = bounds.getFirst();
maxEnd = bounds.getSecond();
}
}
//substring excludes end so we want to get that character too
return s.substring(maxStart, maxEnd + 1);
}
//helper for longestPalindromicSubstringManacher
//adds start and end of string characters as well as separators between each character in the given string
//to pad for both even and odd length palindromes
private static String expandStringManacher(String s){
//more efficient than StringBuffer!
StringBuilder sb = new StringBuilder();
sb.append(MANACHER_START_STRING);
sb.append(MANACHER_CHAR_SEP);
for(int i = 0; i < s.length(); i++){
sb.append(s.charAt(i));
sb.append(MANACHER_CHAR_SEP);
}
sb.append(MANACHER_END_STRING);
return sb.toString();
}
/**
* Given a string, find the longest palindromic substring using Manacher's algorithm.
* @param s the given string.
* @return the longest palindromic substring in this string. If there are multiple ones, return the first one.
*/
public static String longestPalindromicSubstringManacher(String s){
if(s == null || s.length() <= 1){
return s;
}
//first we need to pad the given string
String paddedString = expandStringManacher(s);
//track here for each character in the new string (so both real characters AND spaces between characters)
//the length of the longest palindrome with center on that character
int[] palindromeLengthAtCenter = new int[paddedString.length()];
//while moving along our string, the current character might fall between the boundaries of a previously
//discovered palindrome, we need to remember what was its center and radius (length on either side)
int currPalindromeCenter = 0, currPalindromeRadius = 0;
/*
Example:
given this string, we run the O(n^2) approach and expand outwards from each position, tracking for each
position the maximum length of a palindrome with center in that position. We consider positions between
characters as centers of even length palindromes (# marks beginning and end of string)
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
# a b a c a b a #
if we expand outwards from each position, when we reach character C in the main loop, we will
run the inner loop and expand successfully all the way to the right until the end of the string.
now we know there is a palindrome of length 7 with center on position 8
this means its boundaries are 0 and 15.
Our calculation so far tells us:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
# a b a c a b a #
0 0 1 0 3 0 1 0 7 ? ? ? ? ? ? ?
When we move forward in the main loop to character B in position 12, we know that he is part of a longer palindrome
since its position is still withing the boundaries of the current one.
This means that on the OPPOSITE, mirrored side of character C we MUST appear again, and it also means that EVERY
other character before and after us between the center C and the right boundary MUST appear on the mirror side as well
(otherwise C wouldn't be the center of a palindrome).
But if EVERY other character appears in that EXACT order, then we are the center of another palindrome long at LEAST
the SAME palindrome found on the mirror side, UP TO the current right boundary (as the space afterwards is not
explored yet from our position).
Our calculation tells us then:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
# a b a c a b a #
0 0 1 0 3 0 1 0 7 ? ? ? 3 ? ? ?
now assume our string was actually longer than what we have, then there might be characters after position 15 that could
contribute in making a longer palindrome with center in B in position 12.
When evaluating B in position 12 it's pointless to explore A in position 13 as we already know from the previous
reflections that B is the center of a palindrome of length 3. We can therefore skip expanding from B itself and just
attempt the expansion from position 15 onwards, which is the known length of the palindrome with center in B position 12.
In the case of character A in position 4 instead, the mirror side tells us he is the center of a palindrome of length 1
which would fall within the current boundaries of our palindrome with center in C:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
# a b a c a b a #
0 0 1 0 3 0 1 0 7 0 1 0 3 ? ? ?
we therefore CANNOT attempt expansion from our current boundaries since A in position 10 does NOT reach that boundary,
however attempting an expansion from A in position 10 itself will immediately fail
therefore we won't execute our inner loop at all
by following this logic for each character in the string, we notice that 2 things happen when we expand:
1- we FAIL to expand immediately
2- we expand from a position farther than our current neighbor if we are part of a bigger palindrome
therefore while expanding we do NOT go over the same characters from the right side multiple times,
particularly, as soon as we managed an expansion until the end of the string, we simply do NOT expand at all
as we can't move forward from the end of the string itself
*/
//start from the very beginning of our padded string (the space just after the start marker)
//we consider each position as a center for a palindrome starting there, as in the O(N^2) case
for(int currCenter = 1; currCenter < paddedString.length() - 1; currCenter++){
//if we are within the radius of a previously discovered palindrome
//we already have some calculation we can reuse based on our past discoveries
if(currCenter < currPalindromeRadius){
//calculate our position mirrored along the center of the current palindrome
int mirrorCenterLocation = 2 * currPalindromeCenter - currCenter;
//how can we reuse from our previous calculation
palindromeLengthAtCenter[currCenter] = Math.min(currPalindromeRadius - currCenter,
palindromeLengthAtCenter[mirrorCenterLocation]);
}
//expand outwards from the boundaries we have, checking if we can find a longer palindrome
//this is the key point: we do NOT always start from this very center IF we already have determined that
//this center is already part of some other palindrome, therefore we do NOT walk again on the whole
//string, but continue outwards from the boundaries set by our location within another palindrome
//this means that no NEW character (anything on the right side) is considered twice
//as we either continue forward with successful expansions which move our boundaries closer
//to the end of our string
//OR
//we immediately fail to expand and stop doing more work
//this means that at some point we will have expanded to the end of the string and cannot continue anymore
//from there, therefore skipping this inner loop entirely
while(paddedString.charAt(currCenter + 1 + palindromeLengthAtCenter[currCenter]) ==
paddedString.charAt(currCenter - (1 + palindromeLengthAtCenter[currCenter]))){
palindromeLengthAtCenter[currCenter]++;
}
//if we are a palindrome whose boundaries exceed the current palindrome boundaries
//we are the new reference palindrome for next parts of the string
if(currCenter + palindromeLengthAtCenter[currCenter] > currPalindromeRadius){
currPalindromeCenter = currCenter;
currPalindromeRadius = currCenter + palindromeLengthAtCenter[currCenter];
}
}
//at the end we do NOT have the longest palindrome data yet!
//we need to scan the array to find which palindrome(s) is longest!
int longestPalindromeCenter = 0, longestPalindrome = 0;
for(int i = 0; i < palindromeLengthAtCenter.length; i++){
if(palindromeLengthAtCenter[i] > longestPalindrome){
longestPalindrome = palindromeLengthAtCenter[i];
longestPalindromeCenter = i;
}
}
//just a minor thing to avoid a useless substring in case the whole string is the longest palindrome
if(longestPalindrome == s.length()){
return s;
}
//need to convert back from padded string to normal string to get the start and end boundaries of the palindrome we have identified
return s.substring((longestPalindromeCenter - 1 - longestPalindrome) / 2,
(longestPalindromeCenter - 1 + longestPalindrome) / 2);
}
/**
* Given a string s which encodes plain text only alphabetic characters as a=1,...,z=26
* determine in how many ways can the given string be decoded.
* @param s the string to decode.
* @return the number of ways the string could be decoded.
*/
public static int countWaysToDecode(String s) {
if (s == null || s.length() == 0) {
return 0;
}
/*
We walk from last character back to the start and verify at each step that we have a valid sequence,
if not we raise error. Invalid sequences are:
- any non digit
- 00
- x0: with x > 2
For each character we look at the previous one to determine if there is an increment in the number of ways
we can decode the string, given two digits we have the following valid combinations:
- 10: only one way, the number 10
- 1x: with x > 0 and x <= 9, two ways, single digits (1 and x) or number (1x)
- 20: only one way, the number 20
- 2x: with x > 0 and x <= 6, two ways, single digits (2 and x) or number (2x)
- xy: with x > 2 and y > 0 and y <= 9, one way, the single digits (x and y)
CAUTION: anytime we encounter a 10 or 20, we must track it as the PREVIOUS digit CANNOT use the 1 or 2 to count as double
decoding since we must use that in pair with the previous zero.
Example:
110 - only 1 way: 1, 10
1620 - two ways: 16, 20 - 1, 6, 20
Therefore we track finding a zero and lock the previous digit to it, we remove the flag only after we successfully process
the previous digit (unless it's again a 0 or 10 or 20)
if we represent this as a graph, each "two ways" possibility represents a branching path, with each subsequent digit
updating ALL branching paths, the number of leaves in the end is our result.
This updating ALL branching paths is expensive, in the order of N
We can see that when we look at a new character, we are interested in checking the previous one only
to determine in which case we are, either branching or not.
Therefore we can represent this as a rolling sum of possibilities up to two digits before and up to the last digit
If the new digit does NOT contribute to a branch, our sum is unaltered, we update our values and continue
If the new digit DOES contribute to a branch, our sum is the combination of possibilities from the branches we
would create, for example:
10 - array of possibilities per each position: [1,0]
0
\
1,0
we see the 0 which does not contribute to a branch, possibilities are 1
we see the 1 which together with the 0 does not contribute to a branch, possibilities are still 1
11 - array of possibilities per each position: [2,1]
1
| \
11 1,1
we see the 1 which does not contribute to a branch, possibilities are 1
we see the 1 which together with the other 1 does contribute to a branch, possibilities are now 2
111 - array of possibilities per each position: [3,2,1]
1
/ \
11 1,1
/ / \
11,1 1,1,1 1,11
the new 1 does branch again adding other possibilities to the previous expandable level, total possibilities are 3
we also notice that each new digit expands from the last two digits only, therefore we do not need to remember
the whole array, but only the last two values and update them correctly at each iteration.
*/
//initialize the possibilities for the first digit (last character)
char last = s.charAt(s.length() - 1);
if(last < '0' || last > '9'){
throw new IllegalArgumentException("String contains non decodable characters");
}
//a string of length one is either 1 possibility or an error
if(s.length() == 1){
if(last == '0') {
throw new IllegalArgumentException("String cannot contain only zero");
}
else return 1;
}
//string cannot start with zero
if(s.charAt(0) == '0'){
throw new IllegalArgumentException("String starts with zero");
}
int sumUpToTwoDigitsBefore = 1;
int sumUpToLastDigit = 1;
//for the first digit it would be 1 + possibilities of empty string
int currSum = sumUpToLastDigit;
//track if we encountered a zero, as it locks the previous valid digit in a single decoding only: 10 or 20
boolean hadZero = false;
//for all other digits, apply our logic
for(int i = s.length() - 2; i >= 0; i--){
char curr = s.charAt(i);
if(curr < '0' || curr > '9'){
throw new IllegalArgumentException("String contains non decodable characters");
}
//only valid 10, 20
if(last == '0'){
if(curr == '0' || curr > '2'){
throw new IllegalArgumentException("String contains invalid sequence");
}
}
//we only branch on cases 1x or 2y with y > 0 and y <= 6
//UNLESS we had a zero, which would lock that digit and render it unavailable for this 1x or 2y match
if(!hadZero &&
((curr == '1' && last != '0') ||
(curr == '2' && last > '0' && last <= '6'))){
currSum = sumUpToLastDigit + sumUpToTwoDigitsBefore;
}
//in all other cases, we are still on the same path, so no additional possibilities appear
//we must handle the zero flag correctly though
else{
//if we are a zero now or we are a valid digit and there was a zero before, we are locked to it
hadZero = curr == '0' || last == '0';
currSum = sumUpToLastDigit;
}
//update our possibilities for next iteration, imagine a sliding window where the new value
//appearing left is our sum
sumUpToTwoDigitsBefore = sumUpToLastDigit;
sumUpToLastDigit = currSum;
//remember the last character we saw
last = curr;
}
return currSum;
}
/**
* Find the longest common substring for the two given strings.
* @param s1 the first string.
* @param s2 the second string.
* @return the longest common substring to the two strings, empty if no common substring exists.
*/
public static String longestCommonSubstring(String s1, String s2){
if(s1 == null || s1.length() == 0 || s2 == null || s2.length() == 0){
return "";
}
/*
Cache the max length of matching substrings for each pair of indices i,j in the two strings
If we are at the beginning of a new substring, first match will be max length 1
Otherwise subsequent matches will be previous max length + 1
01234
abcba
dbcbe
starting at a, there is no match for it in the other string
starting at b, we find a first match in position 1 in the other string, then a second match in position 3
starting at c, we find a first match in position 2 in the other string, however at the previous iteration
we had already found a match (i-1, j-1) therefore we expand on that match
we keep track of the longest substring found each time and of the index where the longest substring ends
*/
int[][] lengths = new int[s1.length()][s2.length()];
int longestEnd = 0, maxLongest = 0;
for(int i = 0; i < s1.length(); i++){
for(int j = 0; j < s2.length(); j++){
//unless there is a match, nothing to do since our matrix is already initialized to all zeros
if(s1.charAt(i) == s2.charAt(j)){
//if either is 0, we are beginning a new search, therefore there can't be any previous match
if(i == 0 || j == 0){
lengths[i][j] = 1;
}
else{
lengths[i][j] = lengths[i - 1][j - 1] + 1;
}
if(lengths[i][j] > maxLongest){
maxLongest = lengths[i][j];
longestEnd = i;
}
}
}
}
//if we had a match, retrieve the longest substring
if(maxLongest > 0){
//from the end of the longest substring, walk back the length of it
//and include first and last character in the substring
return s1.substring(longestEnd - maxLongest + 1, longestEnd + 1);
}
return "";
}
/**
* Given a string s and an integer K, find the longest substring with K unique characters (even repeated) in it.
* @param s the given string.
* @param k the number of unique characters allowed in the substring.
* @return the longest substring with K unique characters.
*/
public static String longestSubstringWithKUniqueCharacters(String s, int k){
if(s == null || k <= 0 || k > s.length()){
return "";
}
/*
We use sliding window technique to walk along the string while tracking for each character where did we see it last
As soon as we have found K unique characters, we check if the current substring length is better than our temporary maximum
and update the partial result accordingly. We repeat this check until there are K unique characters available in the current
substring.
Until we find K unique characters, we simply keep walking and track each character we see, as we can't yet produce a result.
When the current character was NOT seen in the current window AND by considering it we would exceed the K limit,
we are in one of the following scenarios (sample limit is 2):
(1) oldest character to evict is on the start of the window
abc
i j
our window starts at i and we now reach character j. We now have 3 unique characters and our limit is 2, we need to evict the oldest
which is A, and reduce our window before continuing. We simply move our window to the next character after A
abc
ij
(2) oldest character to evict appears again within our window
abcba
i j
our window starts at i and we now reach character j. We have again 3 unique characters within our window, we need to evict the oldest
which is B and reduce our window. However we cannot simply move to the next, as we would still have 3 unique characters afterwards
We therefore need to jump to the last occurrence of that character (NOT after it)
Every other character that we have found in between the two occurrences has to be removed as well, since the jump would cut them
out anyway.
abcba
ij
To differentiate the cases, we apply some logic and in case (2) we do not jump directly, rather, we move the window start pointer
forward, deleting from our map all characters we encounter in between.
Additionally, we need to remember to KEEP the last known occurrence of the character at our window start range (B) which we definitely
have deleted while shrinking the window
*/
//key = character, value = last index we saw it
Map<Character, Integer> characterLastOccurrences = new HashMap<>();
//add first character to map immediately
characterLastOccurrences.put(s.charAt(0), 0);
//initially the longest substring is the single character we have
//start and end index of the substring are on that character position and our window starts from there as well
int maxLongest = 1, start = 0, end = 0, startRange = 0;
//walk from the second character onwards
for(int curr = 1; curr < s.length(); curr++){
char currChar = s.charAt(curr);
//if we have seen this already, update its last known location
if(characterLastOccurrences.containsKey(currChar)){
characterLastOccurrences.put(currChar, curr);
}
//otherwise we need to determine if there is eviction to perform
else{
//if we had already K unique characters, we need to remove enough from the oldest one to make
//space for this new one
if(characterLastOccurrences.size() == k){
//if last known position of oldest character to evict is same as start window
//simply move over to next character
//otherwise jump to last known position of character at start window and evict also all others
//found in between
int lastOccurrence = characterLastOccurrences.get(s.charAt(startRange));
//if we jump, we need to remember that as the eviction logic would also remove a valid character from the map
boolean didJump = false;
int jumpToStart;
if(startRange == lastOccurrence ){
jumpToStart = startRange + 1;
}
else {
jumpToStart = lastOccurrence;
didJump = true;
}
//evict all characters until we reach the new window start location
while(startRange < jumpToStart){
characterLastOccurrences.remove(s.charAt(startRange));
startRange++;
}
//if we jumped, we will have deleted a valid character from the map too, which is the new window start location
//we need to reinsert it back
if(didJump){
characterLastOccurrences.put(s.charAt(startRange), startRange);
}
}
//whether we evicted or not, we always add current character to map
characterLastOccurrences.put(currChar, curr);
}
//as long as we have found exactly K unique characters, we keep updating our partial result for longest substring
if(characterLastOccurrences.size() == k) {
if (curr - startRange + 1 > maxLongest) {
maxLongest = curr - startRange + 1;
start = startRange;
end = curr;
}
}
}
//could be our string did not have K unique characters, in that case there is no result
if(maxLongest < k){
return "";
}
//otherwise return the longest substring we found
return s.substring(start, end + 1);
}
/**
* Given a string and a set of words, find the minimum number of deletions required to transform
* the given string into a valid word.
* @param s the string to alter.
* @param words the valid words.
* @return the minimum number of deletions required to transform the given string in to a valid word, -1 if
* no word can be created from the given string.
*/
public static int minDeletionsToFormDictionaryWord(String s, Set<String> words){
if(s == null || s.length() == 0 || words == null || words.isEmpty()){
return -1;
}
//if our string is a word, return immediately
if(words.contains(s)){
return 0;
}
/*
From starting string, do a BFS testing each time a smaller string where a character is removed
By tracking which strings we have seen, we avoid doing duplicate work
The first branch that reaches a valid result, is the minimum number of deletions required
*/
Set<String> seen = new HashSet<>();
//queue of pairs(string, deletions so far)
Queue<Pair<String, Integer>> strings = new LinkedList<>();
strings.add(new Pair<>(s, 0));
while(!strings.isEmpty()){
Pair<String, Integer> curr = strings.poll();
String currString = curr.getFirst();
//since BFS will walk nodes in order, we won't ever get back to a longer string than us
//we therefore don't need to keep all strings in the set, but only the strings that are currently
//in the queue
seen.remove(currString);
//for each character in this string, generate new smaller string without a single character
for(int i = 0; i < currString.length(); i++){
//substring is (includedIndex, excludedIndex) - we exclude char at index i
String newString = currString.substring(0, i) + currString.substring(i + 1);
//no need to push this string to bottom of queue if we already have a result
if(words.contains(newString)){
//remember to add the deletion we just performed to our result
return curr.getSecond() + 1;
}
//if we didn't see the new string yet, add to queue and mark as seen
//this will prevent us from enqueueing already seen words at this level
if(!seen.contains(newString)){
strings.add(new Pair<>(newString, curr.getSecond() + 1));
seen.add(newString);
}
}
}
return -1;
}
/**
* Given two strings find the Levenshtein distance. That is the minimum number of deletions, insertions or replacements
* necessary to transform one string into the other.
* @param start the start string.
* @param end the target string.
* @return the Levenshtein distance.
*/
public static int editDistance(String start, String end) {
if (start == null && end == null) {
return 0;
}
if (start == null || start.length() == 0) {
return end.length();
}
if (end == null || end.length() == 0) {
return start.length();
}
int min = Integer.MAX_VALUE;
final char WILDCARD = '?';
Queue<Pair<String, Integer>> intermediates = new LinkedList<>();
intermediates.add(new Pair<>(start, 0));
Set<String> seen = new HashSet<>();
while(!intermediates.isEmpty()){
Pair<String, Integer> curr = intermediates.poll();
String s = curr.getFirst();
seen.remove(s);
//if string is longer delete a character
if(s.length() > end.length()){
for(int i = 0; i < s.length(); i++){
String next = s.substring(0, i) + s.substring(i + 1);
if(!seen.contains(next)) {
seen.add(next);
intermediates.add(new Pair<>(next, curr.getSecond() + 1));
}
}
}
//if string is shorter add a character
//we do not add all possible characters but only a wildcard, later we can replace it with want we want for free
if(s.length() < end.length()){
for(int i = 0; i < s.length(); i++){
String next = s.substring(0, i + 1) + WILDCARD + s.substring(i + 1);
if(!seen.contains(next)) {
seen.add(next);
intermediates.add(new Pair<>(next, curr.getSecond() + 1));
}
}
}
//same length, we check how many replacements we have to do
//wildcards count as 0 replacement as the act of adding it is the edit cost, we now choose any character we need
if(s.length() == end.length()){
int count = curr.getSecond();
for(int i = 0; i < s.length(); i++){
if(s.charAt(i) != WILDCARD && s.charAt(i) != end.charAt(i)){
count++;
//if our count is equal or more than min, no need to continue as we won't be the best solution
if(count >= min) {
break;
}
}
}
if(count < min){
min = count;
}
}
}
return min;
}
/**
* Given two strings find the Levenshtein distance. That is the minimum number of deletions, insertions or replacements
* necessary to transform one string into the other.
* This method uses Wagner-Fischer algorithm.
* @param start the start string.
* @param end the target string.
* @return the Levenshtein distance.
*/
public static int editDistanceWagnerFischer(String start, String end){
if(start == null && end == null) {
return 0;
}
if(start == null || start.length() == 0){
return end.length();
}
if(end == null || end.length() == 0){
return start.length();
}
int[][] edits = new int[start.length() + 1][end.length() + 1];
for(int i = 0; i < edits.length; i++){
edits[i][0] = i;
}
for(int j = 0; j < edits[0].length; j++){
edits[0][j] = j;
}
for(int i = 1; i < edits.length; i++){
for(int j = 1; j < edits[0].length; j++){
int cost = 0;
if(start.charAt(i - 1) != end.charAt(j - 1)){
cost = 1;
}
edits[i][j] = Math.min(edits[i - 1][j] + 1,
Math.min(edits[i][j - 1] + 1,
edits[i - 1][j - 1] + cost)
);
}
}
return edits[edits.length - 1][edits[0].length - 1];
}
/**
* Given a string, build the Knuth–Morris–Pratt table.
* @param word the given string.
* @return the KMP table of indexes of prefixes in the given string.
*/
public static int[] buildKMPTable(String word){
int[] prefix_table = new int[]{};
if(word == null || word.length() == 0){
return prefix_table;
}
prefix_table = new int[word.length() + 1];
prefix_table[0] = -1;
int pos = 1, candidate_idx = 0;
while(pos < word.length()){
if(word.charAt(pos) == word.charAt(candidate_idx)){
prefix_table[pos] = prefix_table[candidate_idx];
}
else {
prefix_table[pos] = candidate_idx;
while(candidate_idx >= 0 && word.charAt(pos) != word.charAt(candidate_idx)){
candidate_idx = prefix_table[candidate_idx];
}
}
pos++;
candidate_idx++;
}
//last matching prefix
prefix_table[pos] = candidate_idx;
return prefix_table;
}
/**
* Given a text and a word, find all occurrences of word in text.
* @param text the given text.
* @param word the word to search for.
* @param searchAll if true, search all occurrences, otherwise returns the first one.
* @return index of start matches for all occurrences of word in text.
*/
public static List<Integer> searchSubstringKMP(String text, String word, boolean searchAll){
return searchSubstringKMP(text, word, searchAll, null);
}
/**
* Given a text and a word, find all occurrences of word in text.
* @param text the given text.
* @param word the word to search for.
* @param searchAll if true, search all occurrences, otherwise returns the first one.
* @param kmp_table the precomputed prefix array for the search word.
* @return index of start matches for all occurrences of word in text.
*/
public static List<Integer> searchSubstringKMP(String text, String word, boolean searchAll, int[] kmp_table){
List<Integer> matches = new LinkedList<>();
if(text == null || word == null || text.length() == 0 || word.length() == 0 || word.length() > text.length()){
return matches;
}
int text_pos = 0, word_pos = 0;
int[] prefix_table = kmp_table;
if(prefix_table == null){
prefix_table = StringUtils.buildKMPTable(word);
}
while(text_pos < text.length()){
if(word.charAt(word_pos) == text.charAt(text_pos)){
word_pos++;
text_pos++;
//0 based index but we just incremented it before so no need to do word_pos + 1
if (word_pos == word.length()){
matches.add(text_pos - word_pos);
if(!searchAll){
return matches;
}
word_pos = prefix_table[word_pos];
}
}
else{
word_pos = prefix_table[word_pos];
if(word_pos < 0){
text_pos++;
word_pos++;
}
}
}
return matches;
}
/**
* Given a matrix of characters and a word, find if the word appears in the matrix. The word can be constructed
* ONLY by choosing left to right or top to bottom characters but NOT mixing the two.
* Uses KMP string search algorithm.
* @param matrix the available characters.
* @param word the word to search for.
* @return true if word appears in the matrix.
*/
public static boolean wordSearchLRTBusingKMP(char[][] matrix, String word){
if(word == null || matrix == null ||
word.length() == 0 ||
matrix.length == 0 || matrix[0].length == 0 ||
(word.length() > matrix.length && word.length() > matrix[0].length)){
return false;
}
//calculate KMP table
int[] prefix_table = StringUtils.buildKMPTable(word);
//we build all strings from all rows and columns, then do a KMP search for the given word on each
StringBuilder sb = new StringBuilder();
//rows
for(int i = 0; i < matrix.length; i++){
//clear string
sb.setLength(0);
for(int j = 0; j < matrix[0].length; j++){
sb.append(matrix[i][j]);
}
//search this word
if(!StringUtils.searchSubstringKMP(sb.toString(), word, false, prefix_table).isEmpty()){
return true;
}
}
//columns
for(int j = 0; j < matrix[0].length; j++){
//clear string
sb.setLength(0);
for(int i = 0; i < matrix.length; i++){
sb.append(matrix[i][j]);
}
//search this word
if(!StringUtils.searchSubstringKMP(sb.toString(), word, false, prefix_table).isEmpty()){
return true;
}
}
return false;
}
/**
* Given a string s and an array of characters, find the shortest substring that includes all characters, even duplicated,
* of the array. Return empty string if not match is found.
* @param chars the input characters.
* @param s the input string.
* @return the shortest substring that includes all characters of the array or empty is none is found.
*/
public static String getShortestUniqueSubstring(char[] chars, String s){
if(chars == null || chars == null || chars.length == 0 || s.length() == 0 || chars.length > s.length()){
return "";
}
//valid chars
Set<Character> valid = new HashSet<>();
for(char c : chars){
valid.add(c);
}
//chars we need to find to have valid substring
Set<Character> missing = new HashSet<>();
missing.addAll(valid);
//key = char, value = last seen position
Map<Character, Integer> lastPositionForChar = new HashMap<>();
/*
sliding window where we keep increasing until we have found all missing chars.
If a char is not valid, we restart from the next.
When we have found all missing chars, we check for best minimum then we try to decrease string by advancing
window start checking if we still have a valid string.
The char to evict must appear after after the new window start. We continue until possible.
*/
int i = 0;
int min = Integer.MAX_VALUE;
int bestStart = 0, bestEnd = 0;
//init first char
int curr = 1;
lastPositionForChar.put(s.charAt(0), 0);
missing.remove(s.charAt(0));
//walk from second character onward
for(int j = 1; j < s.length(); j++){
char currChar = s.charAt(j);
//if this is not a valid character, we have to restart from the next
//move window start to j + 1 so we skip this invalid character
if(!valid.contains(currChar)){
missing.addAll(valid);
i = j + 1;
continue;
}
//update last seen for this char and remove curr from missing ones, then update length of current substring
lastPositionForChar.put(currChar, j);
missing.remove(currChar);
curr++;
//if we have found all missing, update best result and try to reduce window size
if(missing.isEmpty()){
if(curr < min){
min = curr;
bestStart = i;
bestEnd = j;
}
//we can't move start of window closer than length of all unique characters to end of window
//try to do so and if the char we drop off from start range would NOT appear in new range, we can't reduce
//and must stop
//otherwise we have a shorter substring, update our result
while(j - i + 1 > chars.length){
int lastPos = lastPositionForChar.get(s.charAt(i));
if(lastPos > i){
i++;
curr--;
if(curr < min){
min = curr;
bestStart = i;
bestEnd = j;
}
}
else{
break;
}
}
}
}
//if we hadn't found any match
if(min == Integer.MAX_VALUE){
return "";
}
return s.substring(bestStart, bestEnd + 1);
}
/**
* Given a filesystem representation, find the length of the longest path to a file.
* Representation is (without spaces):
* root \n \t dir \n \t \t file_in_dir.ext
* Files will always have a dot followed by extension.
* Directory names cannot contain a dot.
* Resulting path is root/dir/file_in_dir.ext
* @param input the string representing the whole filesystem.
* @return the length of the longest path to a file in the filesystem.
*/
public static int longestFilesystemPath(String input){
if(input == null || input.isEmpty()){
return 0;
}
//IMPORTANT: we assume input string is well formed, for example we can't have a string \tasd\tlol
//otherwise this approach will NOT work!!
/*
Similar to parentheses matching, we can keep adding lengths of portions of path to a stack
where the last (lowest) level is always on top.
For each item we parse, we calculate its length and (if it is a filename) store in a max appropriately.
The length is length of last level before us (top of stack) + our length, we also need to convert each level to a /
so subtract level + 1, example:
"root \n \t dir \n \t \t file_in_dir.ext" is "root / dir / file_in_dir.ext" where we ignore \n and each group of \t became a single /
4 0 2 3 0 2 2 15 4 1 3 1 15
- level + 1 is to add a single / in place of each group of \t since we use lastIndexOf method which returns the
index BEFORE the last match for the given pattern, or -1 if it is not found
Each time we know at what level we are by counting the number of staring \t we find.
When our stack has more items the the current level, it means we navigated up from the last position,
so we pop elements until the stack contains exactly as many items as our current level.
Since root is level 0 and stack with one item has size 1, we compare with level + 1!!
Example:
root \n \t dir \n \t \t file_in_dir.ext \n \t \t other_file.ext
"root" is level 0, and length 4, push 4 to stack
"dir" is level 1, and length 3, giving a total path of 7 (last level was 4), push 7 to stack
"file_in_dir.ext" is level 2 and length 15, giving a total of 22 (last level was 7), push 22 to stack
Additionally, since "file_in_dir.ext" is a filename (it contains a dot) update max to 22
"other_file.ext" is level 2 but stack has 3 elements, pop one off to reach our level
we are length 14, giving a total of 21, push 21 to stack
This is also a filename, but it's not longer than the max, leave it as is
At the end we will have our max in our variable
*/
//stack will track current length for each path portion in our input up to that point
//start with length 0 for root level
Stack<Integer> stack = new Stack<>();
stack.push(0);
int max = 0;
int currLevel = 0;
int currLength = 0;
//split splits on given char AND removes it from the result string
//eg asd\nlol gives asd, lol
String[] paths = input.split("\n");
for(String path : paths){
//lastIndexOf gives -1 if not found or the index BEFORE START portion of matched substring
//eg: "\t\tasd" gives 1, since the last match for \t starts AFTER index 1
//we need to add 1 to get correct level
currLevel = path.lastIndexOf("\t") + 1;
//if our stack has more items than current level, we need to remove elements until we get to the correct level
//since we are expanding from there and we might have navigated back up from a deeper position
//level + 1 since level 0 is one item in the stack!
while(stack.size() > currLevel + 1){
stack.pop();
}
//at this position the total length from root is
//length up to this level (top of stack) + our length + conversion of all \t to /
currLength = stack.peek() + path.length() - currLevel + 1;
stack.push(currLength);
//if this element is a file, we have a full path to file and need to track the max length
//we remove 1 from total length since we added a / at the end in the previous operation
if(path.contains(".") && max < currLength - 1){
max = currLength - 1;
}
}
return max;
}
/**
* Given a text representing a compressed string, return the uncompressed version.
* Compression works as such: if a substring is repeated K times, we represent as K[substring]
* which can be nested, example K[ssL[a]] means we repeat 'a' L times (call it T) and then repeat 'ssT' K times.
* K is > 0.
* @param s the compressed string.
* @return the uncompressed string.
*/
public static String decodeString(String s){
if(s == null || s.isEmpty()){
return "";
}
/*
Walk on each character of the string, we have the following scenarios:
- c is character, add it to current string we are building and continue
- c is digit, gather all digits composing the number and store the number in a stack. The string we had up to
this point will appear in the output BEFORE the string that will be repeated K times, save that in a stack
Example abc2[d] means abc will appear BEFORE dd which we will be able to build when we reach the matching closed bracket
- c is [, we handle this case as part of the previous one as a well formed string has format number[string]
so we stop reading digits when we encounter the open bracket
- c is ], the string we had up to this point must be repeated K times, based on the last number we read, pop
the number from the stack and the string to place BEFORE repeating the current one from the other stack.
append to the string BEFORE the current one K times the current string
the result is the new current string so far, which is our solution up to this point
When we reach end of the input string, we have the full reconstruction in the StringBuilder
*/
StringBuilder sb = new StringBuilder();
Stack<StringBuilder> strings = new Stack<>();
Stack<Integer> counts = new Stack<>();
for(int i = 0; i < s.length(); i++){
char c = s.charAt(i);
//if this is digit, keep reading until we find '[' so we know how many repetitions to do
if(Character.isDigit(c)){
int count = 0;
while(Character.isDigit(c)){
//keep adding new digit to the least significant place in this number
//while increasing the decimal position of the previous ones
count = count * 10 + (c - '0');
i++;
c = s.charAt(i);
}
//when we reach here c is '['
//store the count and the current string in stacks. The current string will be placed BEFORE
//the result of evaluating the expression within the brackets
counts.push(count);
strings.push(new StringBuilder(sb));
//we stored the string so far, so clear the stringbuilder
sb.setLength(0);
}
else if(c == ']'){
//we reconstruct the string within the brackets by repeating it the correct amount of times
//the string we saved on the stack appears BEFORE the repeated current one
StringBuilder stringBeforeRepeat = strings.pop();
int count = counts.pop();
//we append at the end of the PREVIOUS string, the repetitions of the current one
while(count > 0){
stringBeforeRepeat.append(sb);
count--;
}
//now the reconstructed string is the result up to this character in the compressed string
sb = stringBeforeRepeat;
}
//if it is a simple char, we accumulate it at the end of the current string and continue
else{
sb.append(c);
}
}
return sb.toString();
}
//helper for fullJustify
//pads the line with the given data and returns the string representing it
//spaceSize = how wide is each space we add
//remainingPad = how many extra spaces we need to add from the left side to correctly justify the text
public static String justifyLine(String[] words, int start, int end, int maxWidth, int spaceSize, int remainingPad, StringBuilder sb){
int numWords = end - start + 1;
int spaces = numWords - 1;
//add all words in this range
while(start <= end){
sb.append(words[start]);
//pad this word if necessary
if(spaces > 0){
//add the minimum spaces between words
for(int j = 0; j < spaceSize; j++){
sb.append(' ');
}
//add one of the remaining padding spaces
if(remainingPad > 0){
sb.append(' ');
remainingPad--;
}
spaces--;
}
//move to next word
start++;
}
//pad the right side if necessary
while(maxWidth - sb.length() > 0){
sb.append(' ');
}
return sb.toString();
}
/**
* Given an array of words and a page size, justify the text so that each line is exactly as wide as the page.
* If only one word can fit on the line or the last line has been added to the text, justify on the right side.
* Otherwise justify in between words, distributing excess padding from the left side.
* @param words the input words.
* @param maxWidth the page size.
* @return a list of justified lines to add to the page.
*/
public static List<String> fullJustify(String[] words, int maxWidth) {
List<String> out = new ArrayList<>();
if(words == null || words.length == 0 || maxWidth < 1){
return out;
}
int start = 0; //points to first word for current line
int end = -1; //points to last word for current line
int currLine = maxWidth; //track remaining space on this line (only words)
int currLength = 0; //track current word length on this line
StringBuilder sb = new StringBuilder();
for(int i = 0; i < words.length; i++){
//add this word to current line if there is enough space to fit it
if(currLine - words[i].length() >= 0){
currLine -= words[i].length();
currLength += words[i].length();
//check if we can fit next word, because we need at least a space in between them
//we still have words left
if(i + 1 < words.length){
//(current length - 1 space - new word) must fit in this line
if(currLine - 1 - words[i + 1].length() >= 0){
//if next word could fit, track we would add a space in between
currLine--;
}
//if we can't fit next word, mark this line as full
else{
currLine = 0;
}
}
//this is the last word, mark this line as full
else{
currLine = 0;
}
//we chose to add this word to this line
end++;
}
//at each previous step, we track whether we have space or not for the next word
//could also be we fill the space with the current word
if(currLine == 0){
//how many words we added
int numWords = end - start + 1;
//we had more words in the line, but this is not the last line
//these lines are padded in between words
if(numWords > 1 && end < words.length - 1){
//how many spaces we need to fill the line
int padding = maxWidth - currLength;
//each break point between words needs at least these spaces
int spaceSize = padding / (numWords - 1);
//any leftovers must be distributed among those spaces starting from the left
int remainingPad = padding % (numWords - 1);
out.add(justifyLine(words, start, end, maxWidth, spaceSize, remainingPad, sb));
}
//only one word in the line or last line, pad on the right
else{
out.add(justifyLine(words, start, end, maxWidth, 1, 0, sb));
}
//reset variable for next line
sb.setLength(0);
currLine = maxWidth;
start = end + 1;
end = start - 1;
currLength = 0;
}
}
return out;
}
/**
* Given a valid unix path, simplify it by removing dots and repeated slashes.
* @param path the unix path to simplify.
* @return the simplified path.
*/
public static String simplifyPath(String path){
if(path == null || path.isEmpty()){
return path;
}
/*
Split the path on separators '/'
If we have multiple separators together, we get empty strings are separation result! eg // is "",""
Then enqueue path pieces, ignoring empty strings and dots.
If we encounter a ".." we remove from tail unless queue is empty.
We then recreate the path reading from head of queue.
*/
LinkedList<String> tmpPath = new LinkedList();
StringBuilder sb = new StringBuilder();
//split returns empty strings when split character is followed immediately by other split characters
String[] tokens = path.split("/");
for(String s : tokens){
//must remove last directory if queue is not empty
if(s.equals("..")){
if(!tmpPath.isEmpty()){
tmpPath.removeLast();
}
}
//ignoring "." and "", we add this folder to the path
else if(!s.equals(".") && !s.isEmpty()){
tmpPath.add(s);
}
}
//path starts with "/" then we place all other directories
sb.append("/");
for(String s : tmpPath){
sb.append(s);
sb.append("/");
}
//if we have more than simple "/" we added on extra "/" at the end, remove it
if(sb.length() > 1){
sb.deleteCharAt(sb.length() - 1);
}
return sb.toString();
}
/**
* Given a palindrome string, change any character in order to form the lexicographically earliest non palindrome.
* @param palindrome the palindrome to alter.
* @return empty string if no solution can be found, the lexicographically earliest non palindrome otherwise.
*/
public static String breakPalindrome(String palindrome) {
//any string with less than 2 chars cannot be made non palindrome
if(palindrome == null || palindrome.length() < 2){
return "";
}
/*
We have two options: change an initial 'a' character in the first half (excluding middle point) or change
a last 'a' or 'b' character in the second half (excluding middle point)
For odd length palindromes, changing the middle point will still yield a palindrome, so we must skip the midpoint.
If first half of the string is all 'a', then changing any might give a non palindrome, however it won't be the
lexicographically earliest, example: 'aa' could give 'ba' but the earliest is 'ab'
This means, if we can't change any 'a' from the left side, we change the last char from the right to either 'a'
or 'b' and will be left with the solution.
*/
//ignore middle of odd length palindrome
int mid = (palindrome.length() / 2) - 1;
int change = -1;
//is there any char which is not 'a', we could change that
for(int i = 0; i <= mid; i++){
if(palindrome.charAt(i) > 'a'){
change = i;
break;
}
}
StringBuilder sb = new StringBuilder(palindrome);
//if we did not find any 'a' in the first half, we change the last char to either 'a' or 'b'
if(change > -1){
sb.setCharAt(change, 'a');
return sb.toString();
}
char replace = 'a';
if(palindrome.charAt(palindrome.length() - 1) == 'a'){
replace = 'b';
}
sb.setCharAt(palindrome.length() - 1, replace);
return sb.toString();
}
/**
* Given two strings return true if and only if two chars in one string can be swapped to create the other string.
* Example:
* aa,aa true
* ab,ab false
* ab,ba true
* @param a first string.
* @param b second string.
* @return true if and only if two chars in one string can be swapped to create the other string.
*/
public static boolean checkBuddyStrings(String a, String b) {
if (a == null || b == null || a.length() != b.length() || a.length() < 2) {
return false;
}
/*
The main issue is that we FORCE a swap, even if strings are equal already.
Walk both strings at same time, counting mismatches. If we ever have more than 2 mismatched characters,
stop and return false as we can only swap two at most (eg: asd,jkl), otherwise track the indices of the mismatched ones.
Also check if a string has any duplicate characters. This is necessary as we MUST perform a swap, even if
strings are equal. In that case, we need to have the possibility to do a harmless swap between two duplicates
(eg: aa,aa is ok but ab,ab is not)
At the end we have the following cases:
- no unmatched chars found: we must force a swap between duplicates, if there are any
- one unmatched char found: we cannot swap it with anything
- exactly two unmatched chars found: we need to verify whether the two strings have matching chars at the inverted
indices so we can swap them
*/
List<Integer> unmatched = new ArrayList<>(2);
Set<Character> aChars = new HashSet<>();
boolean hasDuplicates = false;
for(int i = 0; i < a.length(); i++){
char aChar = a.charAt(i);
//count this mismatch, but allow no more than 2 overall
//case asd,jkl
if(aChar != b.charAt(i)){
if(unmatched.size() == 2){
return false;
}
unmatched.add(i);
}
//otherwise, if chars are same, check if string contains duplicates
//cases: aa,aa and ab,ab
else {
if(aChars.contains(aChar)){
hasDuplicates = true;
}
else {
aChars.add(aChar);
}
}
}
//true only if we ha no unmatched chars and at least a duplicate to use OR
//we have TWO unmatched chars and can swap them
return (unmatched.isEmpty() && hasDuplicates) ||
(unmatched.size() == 2 &&
a.charAt(unmatched.get(0)) == b.charAt(unmatched.get(1)) &&
a.charAt(unmatched.get(1)) == b.charAt(unmatched.get(0)));
}
/**
* Given two strings find if the first one can be rotated any number of times to produce the second one.
* @param s the initial string.
* @param rotated the target string.
* @return true if s can be rotated any amount of times to produce rotated.
*/
public static boolean isRotation(String s, String rotated){
if(s == null){
return rotated == null;
}
if(rotated == null){
return s == null;
}
if(s.length() != rotated.length()){
return false;
}
if(s.length() == 0){
return true;
}
/*
All rotations of s are contained in s + s (s concatenated with itself)
We can use KMP algorithm to search for the first match of rotated in s + s, if it exists, then
s can be rotated to form our target.
*/
return !searchSubstringKMP(s + s, rotated, false).isEmpty();
}
/**
* Given a list of strings, group together all the ones that are anagrams of each other.
* @param strings the input strings.
* @return a list of lists of strings that are anagrams of each other.
*/
public static List<List<String>> groupAnagrams(String... strings){
List<List<String>> res = new ArrayList<>();
if(strings == null || strings.length == 0){
return res;
}
/*
We encode each string to a specific compact representation in the form Xchar1..YcharN
Then all anagrams will have the same encoding and we can use a map to quickly look up which strings
are anagrams of each other.
*/
Map<String, List<String>> anagrams = new HashMap<>();
//0 = 'a' ... 25 = 'z'
int[] frequencies;
for(String s : strings){
frequencies = new int[26];
//convert each char into 0 - 25 integer representation and count number of appearances
for(int i = 0; i < s.length(); i++){
int c = s.charAt(i) - 'a';
frequencies[c]++;
}
StringBuilder sb = new StringBuilder();
//convert the frequencies array to a string in the form Xchar1..YcharN
for(int i = 0; i < frequencies.length; i++){
sb.append(frequencies[i]);
sb.append(i + 'a');
}
//add this string to its anagram group
List<String> group = anagrams.getOrDefault(sb.toString(), new ArrayList<>());
group.add(s);
anagrams.put(sb.toString(), group);
}
for(List<String> l : anagrams.values()){
res.add(l);
}
return res;
}
}
package com.blogspot.groglogs.test.stringutils;
import com.blogspot.groglogs.stringutils.StringUtils;
import org.junit.Test;
import static org.junit.Assert.assertFalse;
import static org.junit.Assert.assertTrue;
public class WordSearchLRTBusingKMPJTests {
char[][] matrix;
String word;
@Test
public void nullEmpty() {
matrix = null;
word = null;
assertFalse("null", StringUtils.wordSearchLRTBusingKMP(matrix, word));
matrix = null;
word = "asd";
assertFalse("null matrix", StringUtils.wordSearchLRTBusingKMP(matrix, word));
matrix = new char[][]{{'c'}, {'a'}};
word = null;
assertFalse("null word", StringUtils.wordSearchLRTBusingKMP(matrix, word));
matrix = new char[][]{};
word = "asd";
assertFalse("empty matrix", StringUtils.wordSearchLRTBusingKMP(matrix, word));
matrix = new char[][]{{'c'}};
word = "asd";
assertFalse("array matrix", StringUtils.wordSearchLRTBusingKMP(matrix, word));
matrix = new char[][]{{'c'}, {'a'}};
word = "";
assertFalse("empty word", StringUtils.wordSearchLRTBusingKMP(matrix, word));
}
@Test
public void wordTooLong(){
matrix = new char[][]{{'c'}, {'a'}};
word = "asd";
assertFalse("word too long", StringUtils.wordSearchLRTBusingKMP(matrix, word));
}
@Test
public void oneCharacter(){
matrix = new char[][]{{'c', 'b'}, {'a', 'd'}};
word = "d";
assertTrue("one characters", StringUtils.wordSearchLRTBusingKMP(matrix, word));
}
@Test
public void wordNotInMatrix(){
matrix = new char[][]{
{'c', 'a', 'r'},
{'a', 's', 'd'},
{'r', 'f', 's'}
};
word = "lol";
assertFalse("word not in matrix", StringUtils.wordSearchLRTBusingKMP(matrix, word));
}
@Test
public void wordInRow(){
matrix = new char[][]{
{'c', 'a', 'r'},
{'a', 's', 'd'},
{'r', 'f', 's'}
};
word = "asd";
assertTrue("word in row", StringUtils.wordSearchLRTBusingKMP(matrix, word));
}
@Test
public void wordInCol(){
matrix = new char[][]{
{'c', 'a', 'r'},
{'a', 's', 'd'},
{'r', 'f', 's'}
};
word = "asf";
assertTrue("word in col", StringUtils.wordSearchLRTBusingKMP(matrix, word));
}
@Test
public void wordInSubmatrix(){
matrix = new char[][]{
{'c', 'a', 'r'},
{'a', 's', 'd'},
{'r', 'f', 's'}
};
word = "ds";
assertTrue("word in submatrix", StringUtils.wordSearchLRTBusingKMP(matrix, word));
}
@Test
public void sample(){
matrix = new char[][]{
{'F', 'A', 'C', 'I'},
{'O', 'B', 'Q', 'P'},
{'A', 'N', 'O', 'B'},
{'M', 'A', 'S', 'S'},
};
word = "FOAM";
assertTrue("FOAM", StringUtils.wordSearchLRTBusingKMP(matrix, word));
word = "MASS";
assertTrue("MASS", StringUtils.wordSearchLRTBusingKMP(matrix, word));
word = "OS";
assertTrue("OS", StringUtils.wordSearchLRTBusingKMP(matrix, word));
word = "OB";
assertTrue("OB", StringUtils.wordSearchLRTBusingKMP(matrix, word));
word = "FACE";
assertFalse("FACE", StringUtils.wordSearchLRTBusingKMP(matrix, word));
}
}
@steghio
Copy link
Author

steghio commented Apr 11, 2017

Full description at:

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment