For each pair of strings, eliminate the characters they have in common

wiTcH_doCtoR just a moment. 1 answers, 0 views
java strings programming-challenge time-limit-exceeded

In the below code there are 3 inputs.

First line of input is the number of testcases for which the program will run where (1<=testcases<=10) and i is an int.

For each testcase
Second and third input will be a String where (1<=Stringlength<=10^5)

Output
Now for the output we need to compare both the strings and remove similar characters from both them. The output will be based on which string encounters 0 length first. if none of them is 0 after completion then it will be a draw.

Time of execution is 1.0 sec for each input but my time for 10^5 strings is 2.0. Is there a way to increase its efficiency based on the time.

import java.io.*;
import java.util.*;


public class MyProg{
public static void main(String[] args) throws IOException
{
    BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
    System.out.println("Enter the number of testcases");
    String ts=br.readLine();
    int testcase=Integer.parseInt(ts);
    for(int i=0;i<testcase;i++)
    {
        System.out.println("Enter the 2 strings");
        String sa=br.readLine().replaceAll("\\s+", "");
        String sb=br.readLine().replaceAll("\\s+", "");
        List<Character> s1 = new ArrayList<Character>();
        List<Character> s2 = new ArrayList<Character>();
        for(char c : sa.toCharArray())
            s1.add(c);
        for(char c : sb.toCharArray())
            s2.add(c);
        for(char c:s2)
        {
                s1.remove((Character)c);

        }

        for(char c:sa.toCharArray())
        {
                s2.remove((Character)c);
        }
        if(s1.size()==0 && s2.size()>0)
            System.out.println("You lose some.");
        else if(s1.size()>0 && s2.size()==0)
            System.out.println("You win some.");
        else
            System.out.println("You draw some.");
    }
}}

1 Answers


Andrew 04/26/2017.

I hate this code, but it is faster.

You said you are only working with strings made of characters from a-z. That means 26 characters. The idea is to use 26 counters, each belonging to a character from a-z.

Go through the first(second) string, and every time you find a character c, you increment(decrement) c's counter by 1.

If every counter is zero, that means the strings are permutations of each other, i.e. it's a draw.

Otherwise if every counter is non-negative, you'll know that the first string won; if every counter is non-positive, you'll know that the second string won.

Finally, if some counters have different signs, then it's again a draw.


You can check if all the counters are non-negative like so.
Set a variable allnonneg to true if the first counter is non-negative. Then loop through the remaining counters.

If during the \$i\$-th iteration you find a counter, which is negative, then you change allnonneg to false. Otherwise you keep allnonneg as it is. If in the end allnonneg is true, then you know that every counter was non-negative. If it's false, then you'll know that there was a counter which was negative. This is because the only way the value of allnonneg can change is if there is a counter which is negative.

To do this manipulation, you need a function f, such that f(allnonneg, charset[i] >= 0) is true precisely when both allnonneg, and charset[i] >= 0 are true. Luckily there's already an operator && which does this, so we get

allnonneg = f(allnonneg, charset[i] >= 0) = allnonneg && (charset[i] >= 0)

which is the same as allnonneg &= (charset[i] >= 0).


private static int decide(String sa, String sb){
    int [] charset = new int[26];

    for(int i = 0; i < sa.length(); charset[sa.charAt(i) - 97] ++, i++);
    for(int i = 0; i < sb.length(); charset[sb.charAt(i) - 97] --, i++);

    boolean allnonneg = charset[i] >= 0;
    boolean allnonpos = charset[i] <= 0;

    for(int i = 1; i < 25; i++) {
        allnonneg &= (charset[i] >= 0);
        allnonpos &= (charset[i] <= 0);
    }

    if(allnonneg && allnonpos)
        return 0; // every counter 0 => draw
    if(allnonneg)
        return 1; // 1st won
    if(allnonpos)
        return 2; // 2nd won
    else
        return 0; // mixed signs => draw
}

Language

Popular Tags