Delete the characters of one string from another string

I've got an interview coming up for which the following is a prospective question:


Given 2 strings, for instance:

• John Lennon

• Paul ON

delete every character from string 1 which corresponds with any
character in string 2 (case exclusive).


So following the anticipated manipulations, the output in our case
would be:



Jhe


I've devised the following program for the same:

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    System.out.printf("Enter 2 strings%n");
    String s1,s2,s3;
    s1=br.readLine();
    s2=br.readLine();
    s3="[";
    for(int j=0;j<s2.length();j++)
    {
       s3+=Character.toLowerCase(s2.charAt(j));
       s3+=Character.toUpperCase(s2.charAt(j));
    }
    s3+="]";
    Pattern p = Pattern.compile(s3);
    Matcher m = p.matcher(s1);
    int[] a = new int[10];
    int k=0;
    while(m.find())
    {
        a[k]=m.start();
        k++;
    }
    int j=0;
    for(int i=0;i<k;i++)
    {
        System.out.print(s1.substring(j, a[i]));
        j=a[i]+1;
    }
    System.out.print(s1.substring(j));

This works seamlessly, but my predicament is that these folks don't want you to just get a bloody veracious output, they want a highly optimized output i.e. spatial and temporal requirements as to your program should to be as minimum as can be. And mine is nowhere near the epitome of the optimal solution

If anybody feels that they can alter my code or come up with something better that'd be optimal, I'd be much obliged!

I'd use an object to hold the compiled version of the process for maximum efficiency. This would allow user to create a stripping tool and re-use it for maximum throughput.

Also you have the opportunity to create Strippers. :)

public class Test {

    /**
     * Use a Stripper to encode the stripping process.
     */
    private static class Stripper {

        /**
         * Boolean lookup for maximimum performance.
         *
         * Could use BitSet to save a little space.
         *
         * Length 256 - assumes ASCII.
         */
        private final boolean[] strip = new boolean[256];

        // Compiles the strip string.
        public Stripper(CharSequence strip) {
            for (int i = 0; i < strip.length(); i++) {
                char ch = strip.charAt(i);
                // Both lowercase and uppercase.
                this.strip[Character.toLowerCase(ch)] = true;
                this.strip[Character.toUpperCase(ch)] = true;
            }
        }

        /**
         * Strips all characters from s that were in the `strip` parameter of
         * the constructor.
         *
         * Note the use of `CharSequence` to avoid premature `toString`.
         *
         * @param s - The source of the data to strip.
         * @return The stripped version of s
         */
        public CharSequence strip(CharSequence s) {
            StringBuilder stripped = new StringBuilder();
            for (int i = 0; i < s.length(); i++) {
                char ch = s.charAt(i);
                if (!strip[ch]) {
                    stripped.append(ch);
                }
            }
            return stripped;
        }
    }

    public static final String strip(String from, String strip) {
        return new Stripper(strip).strip(from).toString();
    }

    public void test() {
        System.out.println("Stripped: " + strip("John Lennon", "Paul ON"));

    }

    public static void main(String args[]) {
        try {
            new Test().test();
        } catch (Throwable ex) {
            ex.printStackTrace(System.err);
        }
    }
}

Correctly prints:


Jhe

This algorithm should have an \$O(n)\$ construction complexity and an \$O(n)\$ processing complexity.

Please forgive the I'd do it a completely different way - this answer was posted before it was moved to Code Review.

Added

It seems a bit of narrative would be useful.

Obviously the desired process comes in two parts, first the setup and second the stripping of characters from the original string. This code performs the setup during the construction of the object by building an array of 256 booleans, one for each possible 8-bit character code. Each boolean holds a true value if the character at this position should be stripped from the string.

This ensures that the absolute minimum needs to be done at process time. All that is required is to take one pass through the string, looking up each character in the boolean array. If we find true then the character is discarded, a false means keep it.

StackExchange Code Review Q#62947, answer score: 5