Unique Substring From Joined Strings in Java

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); } }
Code language: Java (java)

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)); } }
Code language: Java (java)

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; } }
Code language: Java (java)

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")); } }
Code language: Java (java)

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|[email protected]\678[90klmnopqrstsrqponmlk","tsrq6\789p[`onmlkvutlsrqp12;345onm|lk'[email protected]")); 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])); } } }
Code language: Java (java)
Tags:
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments