Sample Problem: Find one extra character

 Problem: Finding an extra character in a string

Suppose we have two strings of different lengths, where the second string has all the characters of the first string except for one extra character. We need to find that extra character.

Examples:

• If the first string is "abcd" and the second string is "cbdae", the extra character is "e".
• If the first string is "kxml" and the second string is "klxml", the extra character is "l".

Method 1: We can sort both strings and compare the characters one by one. If we find a mismatch, the extra character will be the character that is present in the second string but not in the first. If there is no mismatch, the last character in the second string will be the extra character.

Method 2: We can use frequency counting to find the extra character. We assume that both strings have only lowercase English letters. We create an array of size 26 to store the frequency of each letter in the second string. Then we decrement the frequency of each letter in the first string. The extra character will have a frequency of 1 in the array.

Method 3: We can use bitwise operators to find the extra character. We combine all characters in both strings and take the bitwise XOR of all the elements. All pairs of characters with the same elements will cancel out. The only character left will be the extra character.

For example, if the first string is "abcd" and the second string is "cbdae", the extra character can be found using Method 2 or Method 3. The output will be "e".

Here's the implementation of the three methods in Java:

Method 1:

// Java implementation of Method 1 import java.util.*;

class ExtraCharacterFinder {

scss
static char findExtra(String s1, String s2)
{
    char[] arr1 = s1.toCharArray();
    char[] arr2 = s2.toCharArray();
    Arrays.sort(arr1);
    Arrays.sort(arr2);
    int i;
    for(i=0; i<arr1.length; i++){
        if(arr1[i]!=arr2[i]){
            return arr2[i];
        }
    }
    return arr2[i];
}

public static void main(String args[])
{
    String s1 = "abcd";
    String s2 = "cbdae";
    System.out.println(findExtra(s1, s2));
}

}

Method 2:

// Java implementation of Method 2 import java.util.*;

class ExtraCharacterFinder {

java
static char findExtra(String s1, String s2)
{
    int[] count = new int[26];
    for(int i=0; i<s2.length(); i++){
        count[s2.charAt(i) - 'a']++;
    }
    for(int i=0; i<s1.length(); i++){
        count[s1.charAt(i) - 'a']--;
    }
    for(int i=0; i<count.length; i++){
        if(count[i]==1){
            return (char) (i+'a');
        }
    }
    return ' ';
}

public static void main(String args[])
{
    String s1 = "abcd";
    String s2 = "cbdae";
    System.out.println(findExtra(s1, s2));
}

}

Method 3:

// Java implementation of Method 3 import java.util.*;

class ExtraCharacterFinder {

scss
static char findExtra(String s1, String s2)
{
    int res = 0;
    for(int i=0; i<s1.length(); i++){
        res ^= s1.charAt(i) ^ s2.charAt(i);
    }
    res ^= s2.charAt(s2.length() - 1);
return (char) res;

}

Explanation of the code:

Method 3 is based on the bitwise XOR operation. We initialize a variable "res" to zero. Then, we loop through both the strings, and for each character, we perform the XOR operation with the corresponding character in the other string. Since XOR of two identical characters is zero, all the characters that are present in both strings will be cancelled out, and the value of "res" will be equal to the ASCII value of the extra character. Finally, we perform the XOR operation with the last character of the second string to get the ASCII value of the extra character.

For example, let's say we have two strings s1 = "abcd" and s2 = "cbdae". We initialize "res" to zero. Then we perform the XOR operation as follows:

res = 0^'a'^'c'^0^'b'^'b'^0^'d'^'d'^0^'e'

Here, XOR of 'a' and 'c' is non-zero, XOR of 'b' and 'b' is zero, XOR of 'd' and 'd' is zero, and XOR of 'e' and zero is 'e'. Therefore, the value of "res" will be equal to the ASCII value of 'e'.

Overall, Method 3 has a time complexity of O(N) and an auxiliary space complexity of O(1).

I hope this helps!