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

Question

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.");
 }
}}

• h.j.k.: Are there any restrictions on the inputs? E.g. reasonable to assume all printable ASCII characters only?
• Dev: The only restriction is characters of a string is between 'a' to 'z' and it contains nothing else.

Answer 1

The cause of your TLE error is this:

 for(char c:s2)
 s1.remove((Character)c);
 for(char c:sa.toCharArray())
 s2.remove((Character)c);

You need to realise that List.remove() is \$O(n)\$ in the length of the list. And in worst case you do this removal \$n\$ times which gives you an \$O(n^2)\$ algorithm which is too slow for this task.

You can be 100% certain that they have a test case that is the maximal number of characters, all the same in both strings as to trigger this worst case behaviour. For example the following:

s1 = "aaaaaaaaaa..." // repeating 10^5 times

s2 = s1

You need to do it in \$O(n)\$ time and to do that you need to figure out a way of doing it without actually removing the characters from the strings. As you didn't link the original question I cannot help you as your description is a bit ambiguous as to how it should work.

Answer 2

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
}

• Dev: It worked fine... Thank you. But can you explain me the use of this for(int i = 0; i < 25; i++) {allnonneg &= (charset[i] >= 0); allnonpos &= (charset[i] <= 0)
• Eman Yalpsid: @wiTcH_doCtoR I've edited in an explanation.

Answer 3

Based on your current implementation I'm going to assume that for strings "ac" and "aaa" we're only removing the first 'a' in both resulting in a draw ("c" and "aa").

Observation 1: The largest of the 2 input strings will always have at least 1 character left after all the removals. This is trivial since we can only remove the number of letters that the smaller string has from the larger one, and by definition it has more letters.

Observation 2: If both strings are of equal length, this will always result in a draw. Either both strings will be emptied completely at the same time, or both will have at least 1 letter left.

So let's use those observations to check as little as possible. First let's write a method that checks if the smallest one will become empty after scrapping all the common letters with the largest one:

private boolean emptyAfterRemovingAll(String smallest, String largest){
 List<Character> listLargest = new ArrayList<Character>();
 listLargest.addAll(largest.toCharArray());
 for(char c : smallest.toCharArray()){
 if(!listLargest.remove(c)){
 //smallest string contains a character that is not in the largest
 return false;
 }
 }
 //able to remove all characters from largest so smallest ends empty.
 return true;
}

Now our for main loop becomes something like this:

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+", "");
 if(sa.length() == sb.length(){
 System.out.println("you draw some.");
 } else if(sa.length() < sb.length()){
 if(emptyAfterRemovingAll(sa,sb)){
 System.out.println("You lose some.");
 } else {
 System.out.println("you draw some.");
 }
 } else {
 if(emptyAfterRemovingAll(sb,sa)){
 System.out.println("You win some.");
 } else {
 System.out.println("you draw some.");
 }
 }
}