The challenge
Write a function that takes two strings, A and B, and returns the length of the longest possible substring that can be formed from the concatenation of either A + B or B + A containing only characters that do not appear in both A and B.
Example:
Given the strings “piquancy” and “refocusing”:
A = “piquancy”
B = “refocusing”
A + B = “piquancyrefocusing”
B + A = “refocusingpiquancy”
Since ‘i’, ‘n’, ‘u’, and ‘c’ appear in both A and B, all acceptable substrings without those characters are:
“p”, “q”, “a”, “yrefo”, “s”, “g” (from A + B)
“refo”, “s”, “gp”, “q”, “a”, “y” (from B + A)
Therefore, it would be correct to return 5: the length of “yrefo”.
The solution in Java code
Option 1:
import static java.util.Arrays.stream;
class FindSubstring {
static int longestSubstring(String a, String b) {
var s = a.chars().mapToObj(c -> "" + (char) c).filter(b::contains).reduce(a + b + a, (x, y) -> x.replace(y, "_"));
return stream(s.split("_")).mapToInt(w -> Math.min((a + b).length(), w.length())).max().orElse(0);
}
}
Option 2:
import static java.util.regex.Pattern.compile;
import static java.lang.Math.min;
public class FindSubstring {
private final static String SPECIAL = "-";
static int longestSubstring(String a, String b){
return compile(SPECIAL).splitAsStream(getReplaced(a,b)).mapToInt(s->min((a+b).length(), s.length())).max().orElse(0);
}
private static String getReplaced(String a, String b) {
return a.chars().mapToObj(c->""+(char)c).filter(b::contains).reduce(a+b+a,(x,y)->x.replace(y, SPECIAL));
}
}
Option 3:
import java.util.Arrays;
import java.util.Optional;
public class FindSubstring {
static int longestSubstring(String a, String b){
if("".equals(a) || "".equals(b)) return (a+b).length();
String[] arrA = a.split("");
String ab = a + b;
String ba = b + a;
for(String s: arrA){
if(b.contains(s)){
ab = ab.replace(s, ",");
ba = ba.replace(s, ",");
}
}
Optional<String> maxAB = Arrays.stream(ab.split(",")).max((x,y) -> x.length() - y.length());
Optional<String> maxBA = Arrays.stream(ba.split(",")).max((x,y) -> x.length() - y.length());
int maxABLength = maxAB.isPresent() ? maxAB.get().length() : 0;
int maxBALength = maxBA.isPresent() ? maxBA.get().length() : 0;
return maxABLength > maxBALength ? maxABLength : maxBALength;
}
}
Test cases to validate our solution
import org.junit.Test;
import static org.junit.Assert.assertEquals;
import org.junit.runners.JUnit4;
public class SubstringTest {
@Test
public void test() {
assertEquals("Example test 1", 8, FindSubstring.longestSubstring("preface","singularity"));
assertEquals("Example test 2", 5, FindSubstring.longestSubstring(" 8684Hh", "7575H--8---"));
assertEquals("Example test 3", 3, FindSubstring.longestSubstring("looking", "zoology"));
}
}
Additional test cases
import org.junit.Test;
import static org.junit.Assert.assertEquals;
import org.junit.runners.JUnit4;
import java.util.*;
public class FindSubstringTests {
public String makeWord() {
String testWord = "";
String charSet = "abcdefghijklMNOPQRSTUVWXYZ1234567890)(*&^% `<>?/}{+=";
Random r = new Random();
for (int i = 0; i < r.nextInt(145)+60; i++){
testWord = testWord += charSet.charAt(r.nextInt(charSet.length()));
}
return testWord;
}
public int lSubstring(String a, String b) {
char[] aPlusB = a.concat(b).toCharArray();
char[] bPlusA = b.concat(a).toCharArray();
// Determine the characters shared by both strings
char[] aChars = a.toCharArray();
char[] bChars = b.toCharArray();
LinkedHashSet<Character> aCharsSet = new LinkedHashSet<Character>();
LinkedHashSet<Character> bCharsSet = new LinkedHashSet<Character>();
for (char character : aChars) {
aCharsSet.add(character);
}
for (char character : bChars) {
bCharsSet.add(character);
}
aCharsSet.retainAll(bCharsSet);
//aCharsSet now holds the characters shared by the strings
int temp = 0;
int maxLength = 0;
// Check each character of aPlusB to see if it's in the set of shared characters
for (int i = 0; i < aPlusB.length; i++) {
if (!aCharsSet.contains(aPlusB[i])) {
// If it isn't, increment temp. temp represents the longest current length of unshared characters.
temp++;
if (temp > maxLength) {
// If temp is greater than the stored max value, update the max value
maxLength = temp;
}
} else {
// Otherwise, reset the length to zero
temp = 0;
}
}
// Repeat the process for B + A
temp = 0;
for (int i = 0; i < bPlusA.length; i++) {
if (!aCharsSet.contains(bPlusA[i])) {
temp++;
if (temp > maxLength) {
maxLength = temp;
}
} else {
temp = 0;
}
}
return maxLength;
}
@Test
public void test() {
assertEquals("Basic test ('preface', 'singularity')", 8, FindSubstring.longestSubstring("preface","singularity"));
assertEquals("Long strings", 607, FindSubstring.longestSubstring(";;;;;;;;;;;;ZZZZ5;;;;;;;;;;;;ZZZZ5;;;;;;;;;;;;ZZZZ5;;;;;;;;;;;;ZZZZ5;;;;;;;;;;;;ZZZZ5;;;;;;;;;;;;ZZZZ5;;;;;;;;;;;;ZZZZ5;;;;;;;;;;;;ZZZZ5;;;;;;;;;;;;ZZZZ5;;;;;;;;;;;;ZZZZ5;;;;;;;;;;;;ZZZZ5;;;;;;;;;;;;ZZZZ5;;;;;;;;;;;;ZZZZ5;;;;;;;;;;;;ZZZZ5;;;;;;;;;;;;ZZZZ5;;;;;;;;;;;;ZZZZ5;;;;;;;;;;;;ZZZZ5;;;;;;;;;;;;ZZZZ5;;;;;;;;;;;;ZZZZ5;;;;;;;;;;;;ZZZZ5;;;;;;;;;;;;ZZZZ5;;;;;;;;;;;;ZZZZ5;;;;;;;;;;;;ZZZZ5;;;;;;;;;;;;ZZZZ5;;;;;;;;;;;;ZZZZ5;;;;;;;;;;;;ZZZZ5;;;;;;;;;;;;ZZZZ5;;;;;;;;;;;;ZZZZ5;;;;;;;;;;;;ZZZZ5;;;;;;;;;;;;ZZZZ5;;;;;;;;;;;;ZZZZ5;;;;;;;;;;;;ZZZZ5;;;;;;;;;;;;ZZZZ5;;;;;;;;;;;;ZZZZ5535533553355355335533553355355335533553355355335533553355533553355335535533553355335535533553355335553355335533553553355335533553553355335533555335533553355355335533553355355335533553355533553355335535533553355335535533553355335553355335533553553355335533553553355335533555335533553355355335533553355355335533553355533553355335535533553355335535533553355335553355335533553553355335533553553355335533555335533553355355335533553355355335533553355533553355335535533553355335535533553355335553355335533553553355335533553553355335533535535533553355335535533553355335535533553355335533553355335535533553355335533113355335533553355335511","01000100101010010101001010101010010001000100101010010101001010101010010001000100101010010101001010101010010001000100101010010101001010101010010001000100101010010101001010101010010001000100101010010101001010101010010001000100101010010101001010101010010001000100101010010101001010101010010001000100101010010101001010101010010001000100101010010101001010101010010001000100101010010101001010101010010001000100101010010101001010101010010001000100101010010101001010101010010001000100101010010101001010101010010001000100101010010101001010101010010001000100Z10101001010100101010101001000100010010101001010100101010101001000100010010101001010100101010101001000100010010101001010100101010101001000100010010101001010100101010101001000100010010101001010100101010101001000100010010101001010100101010101001000100010010101001010100101010101001000100010010101001010100101010101001000100010010101001010100101010101001000100010010101001010100101010101001001"));
assertEquals("Anagrams ('tablets', 'battles')", 0, FindSubstring.longestSubstring("tablets","battles"));
assertEquals("Whitespace and escape characters", 5, FindSubstring.longestSubstring(" \t","\n445 "));
assertEquals("Substring entirely in B", 6, FindSubstring.longestSubstring("bbbbbbbbbbbbbbbbbbbbbbbbbbbbbb","beliefs"));
assertEquals("Substring entirely in A", 6, FindSubstring.longestSubstring("hotdogs","sssssssssssssssssss"));
assertEquals("Substring mid A", 3, FindSubstring.longestSubstring("e1222111100011112221f","12eeeeeeeffffffff"));
assertEquals("Substring mid B", 4, FindSubstring.longestSubstring("&&&&&&&&&&&&&&$$$$$$$$$$$$GGGG","$$$$$$$$$G$$$$$hamo&&&&&&&&&&&&&&&&&&&"));
assertEquals("No shared characters ('rhythms', 'logician')", 15, FindSubstring.longestSubstring("rhythms","logician"));
assertEquals("Lots of shared characters", 6, FindSubstring.longestSubstring("abcd`efgh';lij1|234@5\678[90klmnopqrstsrqponmlk","tsrq6\789p[`onmlkvutlsrqp12;345onm|lk'jihgfedcba0uvwxyz@"));
assertEquals("Two empty strings", 0, FindSubstring.longestSubstring("",""));
assertEquals("One empty string", 8, FindSubstring.longestSubstring("","06032016"));
// THE RANDOM TESTS!!!!!!!!
String[] randomTestsA = {makeWord(), makeWord(),makeWord(),makeWord(),
makeWord(), makeWord(), makeWord(), makeWord(), makeWord(), makeWord(),
makeWord(), makeWord(), makeWord(), makeWord(), makeWord(), makeWord(),
makeWord(), makeWord(), makeWord(), makeWord(), makeWord(), makeWord(),
makeWord(), makeWord(), makeWord(), makeWord(), makeWord(), makeWord(),
makeWord(), makeWord(), makeWord(), makeWord(), makeWord(), makeWord(),
makeWord(), makeWord(), makeWord(), makeWord(), makeWord(), makeWord(),
makeWord(), makeWord(), makeWord(), makeWord(), makeWord(), makeWord(),
makeWord(), makeWord(), makeWord(), makeWord(), makeWord(), makeWord(),
makeWord(), makeWord(), makeWord(), makeWord(), makeWord(), makeWord()};
String[] randomTestsB = {makeWord(), makeWord(),makeWord(),makeWord(),
makeWord(), makeWord(), makeWord(), makeWord(), makeWord(), makeWord(),
makeWord(), makeWord(), makeWord(), makeWord(), makeWord(), makeWord(),
makeWord(), makeWord(), makeWord(), makeWord(), makeWord(), makeWord(),
makeWord(), makeWord(), makeWord(), makeWord(), makeWord(), makeWord(),
makeWord(), makeWord(), makeWord(), makeWord(), makeWord(), makeWord(),
makeWord(), makeWord(), makeWord(), makeWord(), makeWord(), makeWord(),
makeWord(), makeWord(), makeWord(), makeWord(), makeWord(), makeWord(),
makeWord(), makeWord(), makeWord(), makeWord(), makeWord(), makeWord(),
makeWord(), makeWord(), makeWord(), makeWord(), makeWord(), makeWord()};
for (int i = 0; i < randomTestsA.length; i++) {
assertEquals("Random test " + i + 1 + "/58" + " (" + randomTestsA[i] + ", " + randomTestsB[i] + ") " , lSubstring(randomTestsA[i],randomTestsB[i]), FindSubstring.longestSubstring(randomTestsA[i],randomTestsB[i]));
}
}
}
