Solution: Find the Difference

Let's solve the Find the Difference problem using the Bitwise Manipulation pattern.

We'll cover the following

Statement

Given two strings, str1 and str2, find the index of the extra character that is present in only one of the strings.

Note: If multiple instances of the extra character exist, return the index of the first occurrence of the character in the longer string.

Constraints:

  • 0≤0 \leq str1.length, str2.length ≤1000\leq 1000
  • Either str2.length == str1.length + 1, or, str1.length == str2.length + 1
  • The strings consist of lowercase English letters.

Solution

So far, you’ve probably brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which one to follow based on considerations such as time complexity and any implementation constraints.

Naive approach

The naive approach is to first sort both the strings. Then loop over the longer string and compare both strings, character by character. Finally, when one extra character is found in the longer string which does not match with the character at the corresponding index in the other string, we break out of the loop and return the index where the comparison failed.

The time complexity of this solution would be O(nlog⁡n+n)O(n \log n + n), that is O(nlog⁡n)O(n \log n). Here, O(nlog⁡n)O(n \log n) is the cost of sorting one of the strings. The space complexity would be O(1)O(1).

Optimized approach using bitwise manipulation

This solution utilizes the bitwise XOR manipulation to single out an extra character between two strings. It uses the property of the XOR operator of excluding matching pairs and leaves the unmatched (extra) character’s ASCII value. Initially, a variable is set to 00, and we iterate through each string, XOR the ASCII values of its characters with the variable, and store the result of each XOR operation in the same variable. Any character present in both strings cancels out because A⊕A=0A⊕A=0. The unmatched character, however, does not cancel out, and its ASCII value remains in the variable after all iterations. This value represents the extra character.

The algorithm proceeds through the following steps:

  1. Initialize a variable, result, with 00 to store the XOR result.

  2. Find the lengths of both strings.

  3. Iterate over the characters of str1, and for each character, do the following operations:

    • Compute the ASCII value of the character.
    • Perform a bitwise XOR operation between the current value of result and the ASCII value.
    • Store the result of the bitwise XOR operation back in result.

  4. Now, iterate over the characters of str2 and repeat the operations performed in step 3 for each character in str2.

  5. After iterating over both strings, the result variable will correspond to the ASCII value of the extra character.

  6. Find and return the index of the extra character from the string with a greater length.

The slides below illustrate how we would like the algorithm to run:

Note: In the following section, we will gradually build the solution. Alternatively, you can skip straight to just the code.

Step-by-step solution construction

Let’s start with the simplest step:

Initialize a variable result with 0. Find the lengths of both strings. Iterate over each character of str1, and for each character, perform a bitwise XOR operation between the current value of result and the ASCII value of the character. Update the result with the computed XOR value every time.

class FindDifference {
  
    public static String printStringWithMarkers(String strn, int pValue) {
      String out = "";
      for (int i = 0; i < pValue; i++) {
        out += String.valueOf(strn.charAt(i));
      }
      out += "«";
      out += String.valueOf(strn.charAt(pValue)) + "»";
      for (int i = pValue + 1; i < strn.length(); i++) {
        out += String.valueOf(strn.charAt(i));
      }
      return out;
    }
    public static int extraCharcterIndex(String str1, String str2) {
      // Initialize the result variable to store the result
      int result = 0;
      // Store the length of str1 in str1Length variable
      int str1Length = str1.length();
      // Store length of str2 in str2Length variable
      int str2Length = str2.length();
      // Traverse the string 1 till the end and perform xor with the result
      System.out.println("\n\tTraversing first string");
      for (int i = 0; i < str1Length; i++) {
        System.out.println("\t\t" + printStringWithMarkers(str1, i));
        System.out.println("\t\tCurrent character: " + str1.charAt(i));
        System.out.println("\t\tresult: " + result);
        System.out.println("\t\tperforming XOR operation");
        System.out.println("\t\t\tresult XOR ASCII(" + str1.charAt(i) + ") = " + result + " XOR " + (int)(str1.charAt(i)));
        // Perform the xor operation with the resul
        result ^= str1.charAt(i);
        System.out.println("\t\tresult: " + result + "\n");
      }
      return 0;
    }
  
  public static void main(String[] args) {
    // Driver code
    // Example - 1
    String[] string1 = {
      "wxyz",
      "cbda",
      "jlkmn",
      "courae",
      "hello"
    };
    String[] string2 = {
      "zwxgy",
      "abc",
      "klmn",
      "couearg",
      "helo"
    };
    for (int i = 0; i < string1.length; i++) {
      System.out.println(i + 1 + ".\tString1 = " + string1[i] + " \n\tString2 = " + string2[i]);
      extraCharcterIndex(string1[i], string2[i]);
      System.out.println(PrintHyphens.repeat("-", 100));
    }
  }
}
Find the Difference

Similar to the first step, now iterate over each character of the str2, and for each character, perform the bitwise XOR operation between the current value of the result and the ASCII value of the character. Again, update the result variable with the computed XOR value every time. After the traversals of both strings, result will contain the ASCII value of the extra character.

This technique works because XOR returns 00 if the bits are the same (both 00 or both 11) and 11 if the bits differ (one is 00, and the other is 11). For example, 111 XOR 111111 \space XOR \space 111 returns 000000, and 101 XOR 010101 \space XOR \space 010 returns 111111. Keeping this property in mind, when we traverse the str2, the common characters between the str1 and str2 cancel out, leaving only the extra character in the result variable.

class Difference {
    public static String printStringWithMarkers(String strn, int pValue) {
      String out = "";
      for (int i = 0; i < pValue; i++) {
        out += String.valueOf(strn.charAt(i));
      }
      out += "«";
      out += String.valueOf(strn.charAt(pValue)) + "»";
      for (int i = pValue + 1; i < strn.length(); i++) {
        out += String.valueOf(strn.charAt(i));
      }
      return out;
    }
    public static int extraCharcterIndex(String str1, String str2) {
      // Initialize the result variable to store the result
      int result = 0;
      int index = 0;
      // Store the length of str1 in str1Length variable
      int str1Length = str1.length();
      // Store length of str2 in str2Length variable
      int str2Length = str2.length();
      // Traverse the string 1 till the end and perform xor with the result
      System.out.println("\n\tTraversing the first string");
      for (int i = 0; i < str1Length; i++) {
        System.out.println("\t\t" + printStringWithMarkers(str1, i));
        System.out.println("\t\tCurrent character: " + str1.charAt(i));
        System.out.println("\t\tresult: " + result);
        System.out.println("\t\tperforming XOR operation");
        System.out.println("\t\t\tresult XOR ASCII(" + str1.charAt(i) + ") = " + result + " XOR " + (int)(str1.charAt(i)));
        // Perform the xor operation with the result
        result ^= str1.charAt(i);
        System.out.println("\t\tresult: " + result + "\n");
      }
      // Traverse the string 2 till the end and perform xor operation with the result
      System.out.println("\n\tTraversing the Second string");
      for (int i = 0; i < str2Length; i++) {
        System.out.println("\t\t" + printStringWithMarkers(str2, i));
        System.out.println("\t\tCurrent character: " + str2.charAt(i));
        System.out.println("\t\tresult:" + result);
        System.out.println("\t\tperforming XOR operation");
        System.out.println("\t\t\tresult XOR ASCII(" + str2.charAt(i) + ") = " + result + " XOR " + (int)(str2.charAt(i)));
        // Perform the xor operation with the result
        result ^= str2.charAt(i);
        System.out.println("\t\tresult: " + result + "\n");
      }
      return 0;
    }
  
    public static void main(String[] args) {
      // Driver code
      // Example - 1
      String[] string1 = {
        "wxyz",
        "cbda",
        "jlkmn",
        "courae",
        "hello"
      };
      String[] string2 = {
        "zwxgy",
        "abc",
        "klmn",
        "couearg",
        "helo"
      };
      for (int i = 0; i < string1.length; i++) {
        System.out.println(i + 1 + ".\tString1 = " + string1[i] + " \n\tString2 = " + string2[i]);
        extraCharcterIndex(string1[i], string2[i]);
        System.out.println(PrintHyphens.repeat("-", 100));
      }
    }
}
Find the Difference

Now, we have the ASCII value of the extra character in the result variable. To find the index of this extra character, we check the length of both strings. Since the extra character is present in the longest string, we return the index of that extra character from the longest string.

class Difference {
    public static String printStringWithMarkers(String strn, int pValue) {
      String out = "";
      for (int i = 0; i < pValue; i++) {
        out += String.valueOf(strn.charAt(i));
      }
      out += "«";
      out += String.valueOf(strn.charAt(pValue)) + "»";
      for (int i = pValue + 1; i < strn.length(); i++) {
        out += String.valueOf(strn.charAt(i));
      }
      return out;
    }
    public static int extraCharcterIndex(String str1, String str2) {
      // Initialize the result variable to store the result
      int result = 0;
      int index = 0;
      // Store the length of str1 in str1Length variable
      int str1Length = str1.length();
      // Store length of str2 in str2Length variable
      int str2Length = str2.length();
      // Traverse the string 1 till the end and perform xor with the result
      System.out.println("\n\tTraversing the first string");
      for (int i = 0; i < str1Length; i++) {
        System.out.println("\t\t" + printStringWithMarkers(str1, i));
        System.out.println("\t\tCurrent character: " + str1.charAt(i));
        System.out.println("\t\tresult: " + result);
        System.out.println("\t\tperforming XOR operation");
        System.out.println("\t\t\tresult XOR ASCII(" + str1.charAt(i) + ") = " + result + " XOR " + (int)(str1.charAt(i)));
        // Perform the xor operation with the result
        result ^= str1.charAt(i);
        System.out.println("\t\tresult: " + result + "\n");
      }
      // Traverse the string 2 till the end and perform xor operation with the result
      System.out.println("\n\tTraversing the Second string");
      for (int i = 0; i < str2Length; i++) {
        System.out.println("\t\t" + printStringWithMarkers(str2, i));
        System.out.println("\t\tCurrent character: " + str2.charAt(i));
        System.out.println("\t\tresult:" + result);
        System.out.println("\t\tperforming XOR operation");
        System.out.println("\t\t\tresult XOR ASCII(" + str2.charAt(i) + ") = " + result + " XOR " + (int)(str2.charAt(i)));
        // Perform the xor operation with the result
        result ^= str2.charAt(i);
        System.out.println("\t\tresult: " + result + "\n");
      }
      // Returning the result based on the condition
      System.out.println("\tResult is the ASCII value of the extra character");
      System.out.println("\t\tExtra character = char(" + result + ") ⟶ " + (char)(result));
      System.out.println("\n\tString 1's length: " + str1.length());
      System.out.println("\tString 2's length: " + str2.length());
      if (str1.length() > str2.length()) {
        index = str1.indexOf((char)(result));
        System.out.println("\tSince String 1's length is greater than string 2's length,\n\tthe extra character is in string 1.");
        System.out.println("\t\t" + printStringWithMarkers(str1, index));
        System.out.print("\tExtra character is '" + str1.charAt(index) + "' ");
        return str1.indexOf((char)(result));
      }
      else {
        index = str2.indexOf((char)(result));
        System.out.println("\tSince String 2's length is greater than string 1's length,\n\tthe extra character is in string 2.");
        System.out.println("\t\t" + printStringWithMarkers(str2, index));
        System.out.print("\tExtra character is '" + str2.charAt(index) + "' " );
        return str2.indexOf((char)(result));
      }
    }
    public static void main(String[] args) {
      // Driver code
      // Example - 1
      String[] string1 = {
        "wxyz",
        "cbda",
        "jlkmn",
        "courae",
        "hello"
      };
      String[] string2 = {
        "zwxgy",
        "abc",
        "klmn",
        "couearg",
        "helo"
      };
      for (int i = 0; i < string1.length; i++) {
        System.out.println(i + 1 + ".\tString1 = " + string1[i] + " \n\tString2 = " + string2[i]);
        System.out.println("at index "  + extraCharcterIndex(string1[i], string2[i]));
        System.out.println(PrintHyphens.repeat("-", 100));
      }
    }
}
Find the Difference

Just the code

Here’s the complete solution to this problem:

class Difference {
    public static int extraCharcterIndex(String str1, String str2) {
      int result = 0;
      int index = 0;
      int str1Length = str1.length();
      int str2Length = str2.length();
      for (int i = 0; i < str1Length; i++) {
        result ^= str1.charAt(i);
      }
      for (int i = 0; i < str2Length; i++) {
        result ^= str2.charAt(i);
      }
      if (str1.length() > str2.length()) {
        index = str1.indexOf((char)(result));
        return index;
      }
      else {
        index = str2.indexOf((char)(result));
        return index;
      }
    }
    public static void main(String[] args) {
      // Driver code
      // Example - 1
      String[] string1 = {
        "wxyz",
        "cbda",
        "jlkmn",
        "courae",
        "hello"
      };
      String[] string2 = {
        "zwxgy",
        "abc",
        "klmn",
        "couearg",
        "helo"
      };
      for (int i = 0; i < string1.length; i++) {
        System.out.println(i + 1 + ".\tString1 = " + string1[i] + " \n\tString2 = " + string2[i]);
        System.out.println("\n\tThe extra character is at index: "  + extraCharcterIndex(string1[i], string2[i]));
        System.out.println(PrintHyphens.repeat("-", 100));
      }
    }
}
Find the Difference

Solution summary

To recap, the solution to this problem can be divided into the following three parts:

  1. Intialize a variable, result, with 00.

  2. Perform a bitwise XOR operation between the current value of result and the ASCII value of each character in str1. Update the value of result with the computed XOR value every time.

  3. Perform a bitwise XOR operation between the current value of result and the characters of str2. Update the value of result each time with the computed XOR value.

  4. result now contains the ASCII value of the extra character. Find and return the index of the extra character from the longer string.

Time complexity

The time complexity of the solution is O(n)O(n), where nn is the length of the strings. Since, we iterate through both the strings once.

Space complexity

The space complexity of the solution above is O(1)O(1), because we used a constant amount of space.

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.