Exactly one swap

JavaView on GFG

Time: O(n)

Space: O(26)

Problem Overview

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

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?