Leetcode 2351. First Letter to Appear Twice

Problem Link: 2351: Leetcode

GitHub repo for more solutions: Git

Leetcode profile: Leetcode: devn007

Geeks for geeks profile: GFG: devnirwal16

Intuition

Approach 1: Using frequency array

Approach

Take a boolean array of 26 elements.

Map each character to index such that a - 0, b - 1,...,z-25.

Iterate through the string and set each index to true.

Before setting any index to be true, check if its true already, if yes return that character.

If we reach at the end of the loop return -1 that means our string only contains unique elements.

Complexity

• Time complexity: O(N)

• Space complexity: O(1)

Code

// Approach 1: Using Frequency array
class Solution {
    public char repeatedCharacter(String s) {
        boolean[] freq = new boolean[26];
        for(char c: s.toCharArray()){
            int index = c - 'a';
            if(freq[index] == true) return truec;
            freq[index] = !freq[index];
        }
        return '-1';
    }
}

Intuition

Approach 2: Using bit masking

Approach

Using a 32-bit number to track 26 alphabet characters.

We are mapping each bit for each character since a number has 32 bit.

If any bit is already set to 1 we return that character

Complexity

• Time complexity: O(N)

• Space complexity: O(1)

Code

class Solution {
    // Approach 2: Bit-wise approach.

    public int setKBit(int num, int k) { // Setting the k-bit to 1 in the number num
        return (1 << k) | num;
    }

    public boolean checkKBit(int num, int k) { // checking if kth bit is already one if yes return true
        return ((1 << k) & num) != 0;
    }

    public char repeatedCharacter(String s) {
        int value = 0;
        for (char c : s.toCharArray()) {
            int k = c - 'a'; // mapping a - 0, b-1, c-2 ... z-25 index
            if (checkKBit(value, k))
                return c; // checking for k bit in the number if set to 1 or not
            value = setKBit(value, k); // setting kth bit to 1 for any character
        }
        return '-1';
    }
}