Constructing Unique String Sequence

Question

I am brushing up on my Java skills by trying to solve the below assignment problem I found on the internet:

Write a Java method that accepts two strings as parameters and returns a string that contains all unique two-character strings whose first character comes from the first string and second character comes from the second string. All two-character strings in your returned string should be separated by a space. Use ordinary string concatenation in your solution. Look at the examples below for a "hint" on how to proceed and look at the String API for methods you can use to simplify your solution.

Example

First string = ABCD
Second string = EFGH
Returned string > AE AF AG AH BE BF BG BH CE CF CG CH DE DF DG DH

How can I improve this code?

package com.assignments.java;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * This is an Assignment Program for Java
 * 
 * @author SaiUpadhyayula
 *
 */

public class JavaAssignmentOne {
    public static void main(String[] args) throws IOException {
        BufferedReader bReader = new BufferedReader(new InputStreamReader(
                System.in));

        System.out.println("Enter First String");
        String firstString = bReader.readLine();

        System.out.println("Enter Second String");
        String secondString = bReader.readLine();

        String returnedString = constructCharSequence(firstString, secondString);
        System.out.println("Returned String : " + returnedString.trim());
    }

    public static String constructCharSequence(String firstString,
            String secondString) throws IOException {

        String biggerString = firstString;
        String smallerString = secondString;
        String returnedString = "";

        // Determine the smaller and bigger Strings from
        // the given two input strings
        if (firstString.length() <= secondString.length()) {
            biggerString = firstString;
            smallerString = secondString;
        } else {
            biggerString = secondString;
            smallerString = firstString;
        }

        // Construct the given required character sequence
        // by iterating over the two input strings

        for (int i = 0; i < biggerString.length(); i++) {
            for (int j = 0; j < smallerString.length(); j++) {

                // As we require unique two-character string
                // check whether the string sequence already exists
                // in the returnedString
                if (!returnedString.contains("" + biggerString.charAt(i)
                        + smallerString.charAt(j) + "")) {
                    returnedString = returnedString + biggerString.charAt(i)
                            + smallerString.charAt(j) + " ";
                }
            }
        }
        return returnedString;
    }
}

Answer 1

Don't declare to throw if you don't throw

The constructCharSequence declares throws IOException but it will never throw that.

Pay attention to the specs

It's extremely important to pay attention to the spec, so you implement what is required, and you don't miss your target, or even, shoot for the wrong target.

In this example:

[...] return a string that contains all unique two-character strings whose first character comes from the first string and second character comes from the second string

For the input strings "ABCD", "EFG" your method returns "EA EB EC ED FA FB FC FD GA GB GC GD", which fails the specs. A passing string would be for example: "AE AF AG BE BF BG CE CF CG DE DF DG"

Watch out for logical errors

Read this:

    if (firstString.length() <= secondString.length()) {
        biggerString = firstString;
        smallerString = secondString;

The code paraphrased: if the first string is shorter, then the bigger string is the first string. Shouldn't that be the other way around? This way would have made more sense:

    if (firstString.length() < secondString.length()) {
        biggerString = secondString;
        smallerString = firstString;

Duplicated code

In these lines, the code for combining the two characters is duplicated:

if (!returnedString.contains("" + firstString.charAt(i) + secondString.charAt(j) + "")) {
    returnedString = returnedString + firstString.charAt(i) + secondString.charAt(j) + " ";

It would be better to put firstString.charAt(i) + secondString.charAt(j) into a local variable and use that in the two expressions.

Half-baked constructCharSequence

The constructCharSequence method is poorly named. Since it's defined to return a String, we already know that it constructs some sort of character sequence, so the name says nothing new. createUniqueCharPairs would be better.

And it doesn't finish the job. It returns a string with an extra space at the end. Callers of this method need extra knowledge of this, and trim if necessary. It would have been better to trim the string before returning.

Inefficient implementation

!returnedString.contains is inefficient. For example, when both strings contain unique characters, the (growing) returnedString will be traversed from start to end in every iteration. You could use a Set or a boolean[] to track the characters that were already used.

Suggested implementation

With the above suggestions applied:

public String createUniqueCharPairs(String firstString, String secondString) {
    Set<Character> seenFirst = new HashSet<>();
    StringBuilder builder = new StringBuilder();

    for (int i = 0; i < firstString.length(); ++i) {
        char first = firstString.charAt(i);
        if (seenFirst.contains(first)) {
            continue;
        }
        seenFirst.add(first);

        Set<Character> seenSecond = new HashSet<>();

        for (int j = 0; j < secondString.length(); ++j) {
            char second = secondString.charAt(j);
            if (seenSecond.contains(second)) {
                continue;
            }
            seenSecond.add(second);

            builder.append(" ").append(first).append(second);
        }
    }
    return builder.substring(1);
}

Although the assignment explicitly said to use string concatenation, the use of a StringBuilder instead is trivially easy to understand, and it's good to adopt good practices like this one early.

I also changed the trimming logic, opting to append space + char1 + char2, and at the end return the result without the first space char. This is slightly more efficient than trimming.

And here are some JUnit tests to verify it actually works as expected:

@Test
public void test_ABCD_EFGH() {
    assertEquals("AE AF AG AH BE BF BG BH CE CF CG CH DE DF DG DH", createUniqueCharPairs("ABCD", "EFGH"));
}

@Test
public void test_ABCD_EFG() {
    assertEquals("AE AF AG BE BF BG CE CF CG DE DF DG", createUniqueCharPairs("ABCD", "EFG"));
}

@Test
public void test_ABAB_EFG() {
    assertEquals("AE AF AG BE BF BG", createUniqueCharPairs("ABAB", "EFG"));
}

@Test
public void test_ABAB_EFEF() {
    assertEquals("AE AF BE BF", createUniqueCharPairs("ABAB", "EFEF"));
}