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:

1
2
3
4
5
6
7
8

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:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

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:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

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

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122

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]));
     }
    }
}