The problem
Write a operate that takes two strings, A and B, and returns the size of the longest doable substring that may be shaped from the concatenation of both A + B or B + A containing solely characters that don’t seem in each A and B.
Instance:
Given the strings “piquancy” and “refocusing”:
A = “piquancy”
B = “refocusing”
A + B = “piquancyrefocusing”
B + A = “refocusingpiquancy”
Since ‘i’, ‘n’, ‘u’, and ‘c’ seem in each A and B, all acceptable substrings with out these characters are:
“p”, “q”, “a”, “yrefo”, “s”, “g” (from A + B)
“refo”, “s”, “gp”, “q”, “a”, “y” (from B + A)
Subsequently, it might be right to return 5: the size of “yrefo”.
The answer in Java code
Choice 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::accommodates).cut back(a + b + a, (x, y) -> x.exchange(y, "_"));
return stream(s.cut up("_")).mapToInt(w -> Math.min((a + b).size(), w.size())).max().orElse(0);
}
}
Choice 2:
import static java.util.regex.Sample.compile;
import static java.lang.Math.min;
public class FindSubstring {
personal last static String SPECIAL = "-";
static int longestSubstring(String a, String b){
return compile(SPECIAL).splitAsStream(getReplaced(a,b)).mapToInt(s->min((a+b).size(), s.size())).max().orElse(0);
}
personal static String getReplaced(String a, String b) {
return a.chars().mapToObj(c->""+(char)c).filter(b::accommodates).cut back(a+b+a,(x,y)->x.exchange(y, SPECIAL));
}
}
Choice 3:
import java.util.Arrays;
import java.util.Optionally available;
public class FindSubstring {
static int longestSubstring(String a, String b){
if("".equals(a) || "".equals(b)) return (a+b).size();
String[] arrA = a.cut up("");
String ab = a + b;
String ba = b + a;
for(String s: arrA){
if(b.accommodates(s)){
ab = ab.exchange(s, ",");
ba = ba.exchange(s, ",");
}
}
Optionally available<String> maxAB = Arrays.stream(ab.cut up(",")).max((x,y) -> x.size() - y.size());
Optionally available<String> maxBA = Arrays.stream(ba.cut up(",")).max((x,y) -> x.size() - y.size());
int maxABLength = maxAB.isPresent() ? maxAB.get().size() : 0;
int maxBALength = maxBA.isPresent() ? maxBA.get().size() : 0;
return maxABLength > maxBALength ? maxABLength : maxBALength;
}
}
Check circumstances to validate our answer
import org.junit.Check;
import static org.junit.Assert.assertEquals;
import org.junit.runners.JUnit4;
public class SubstringTest {
@Check
public void check() {
assertEquals("Instance check 1", 8, FindSubstring.longestSubstring("preface","singularity"));
assertEquals("Instance check 2", 5, FindSubstring.longestSubstring(" 8684Hh", "7575H--8---"));
assertEquals("Instance check 3", 3, FindSubstring.longestSubstring("trying", "zoology"));
}
}
Extra check circumstances
import org.junit.Check;
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.size()));
}
return testWord;
}
public int lSubstring(String a, String b) {
char[] aPlusB = a.concat(b).toCharArray();
char[] bPlusA = b.concat(a).toCharArray();
// Decide the characters shared by each 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;
// Test every character of aPlusB to see if it is within the set of shared characters
for (int i = 0; i < aPlusB.size; i++) {
if (!aCharsSet.accommodates(aPlusB[i])) {
// If it is not, increment temp. temp represents the longest present size of unshared characters.
temp++;
if (temp > maxLength) {
// If temp is bigger than the saved max worth, replace the max worth
maxLength = temp;
}
} else {
// In any other case, reset the size to zero
temp = 0;
}
}
// Repeat the method for B + A
temp = 0;
for (int i = 0; i < bPlusA.size; i++) {
if (!aCharsSet.accommodates(bPlusA[i])) {
temp++;
if (temp > maxLength) {
maxLength = temp;
}
} else {
temp = 0;
}
}
return maxLength;
}
@Check
public void check() {
assertEquals("Primary check ('preface', 'singularity')", 8, FindSubstring.longestSubstring("preface","singularity"));
assertEquals("Lengthy 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 completely in B", 6, FindSubstring.longestSubstring("bbbbbbbbbbbbbbbbbbbbbbbbbbbbbb","beliefs"));
assertEquals("Substring completely 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("A number of shared characters", 6, FindSubstring.longestSubstring("abcd`efgh';lij1|[email protected]678[90klmnopqrstsrqponmlk","tsrq6789p[`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.size; i++) {
assertEquals("Random check " + i + 1 + "/58" + " (" + randomTestsA[i] + ", " + randomTestsB[i] + ") " , lSubstring(randomTestsA[i],randomTestsB[i]), FindSubstring.longestSubstring(randomTestsA[i],randomTestsB[i]));
}
}
}