Exactly one swap

JavaView on GFG

Time: O(n)

Space: O(26)

Intuition

Check if string can become another with exactly one swap of characters.

Algorithm

1Find positions of differences. If 2 differences: check swapping those positions makes strings equal.
2If 0 differences: must have at least one duplicate character (swap same chars).

Common Pitfalls

•Exactly 2 diff positions: verify cross-swap. 0 differences: valid only if duplicate char exists for identity swap.

Exactly one swap.java

Java

// Approach: Count character frequencies. Check if exactly one swap can sort or satisfy the condition.
// Time: O(n) Space: O(26)
class Solution {
    int countStrings(String s) {
        int n = s.length();
        long totalSwaps = (long) n * (n - 1) / 2;

        int[] freq = new int[26];
        for (char c : s.toCharArray())
            freq[c - 'a']++;

        long duplicateSwaps = 0;
        boolean hasDuplicateChar = false;
        for (int f : freq) {
            if (f > 1) {
                hasDuplicateChar = true;
                duplicateSwaps += (long) f * (f - 1) / 2;
            }
        }

        long distinct = totalSwaps - duplicateSwaps;

        if (hasDuplicateChar)
            distinct += 1;

        return (int) distinct;
    }
}

Was this solution helpful?