Welcome to Subscribe On Youtube

3992. Rearrange String to Avoid Character Pair

Description

You are given a string s and two distinct lowercase English letters x and y.

Rearrange the characters of s to construct a new string t such that:

  • t is a permutation of s.
  • Every occurrence of y appears before every occurrence of x in t.

Return any valid string t.

 

Example 1:

Input: s = "aabc", x = "a", y = "c"

Output: "cbaa"

Explanation:

The string "cbaa" is a permutation of "aabc", and every occurrence of 'c' appears before every occurrence of 'a'.

Example 2:

Input: s = "dcab", x = "d", y = "b"

Output: "cabd"

Explanation:

The string "cabd" is a permutation of "dcab", and every occurrence of 'b' appears before every occurrence of 'd'.

Example 3:

Input: s = "axe", x = "o", y = "x"

Output: "axe"

Explanation:

The string "axe" is already valid. Since 'o' does not occur in the string, the required condition is automatically satisfied.

 

Constraints:

  • 1 <= s.length <= 100
  • s consists of lowercase English letters.
  • x and y are lowercase English letters.
  • x != y

Solutions

Solution 1: Two Pointers

We need to construct a permutation $t$ of $s$ such that every occurrence of $y$ appears before every occurrence of $x$. There are no extra constraints on the other characters.

Therefore, it suffices to move all occurrences of $y$ to the front of the string. Traverse the string with two pointers: $i$ points to the next position where a $y$ should be placed, and $j$ scans from left to right. Whenever $t[j] = y$, swap $t[i]$ with $t[j]$ and increment $i$. After the scan, the prefix of $t$ consists entirely of $y$, which naturally satisfies the requirement that all $y$ appear before all $x$.

The time complexity is $O(n)$, and the space complexity is $O(n)$, where $n$ is the length of $s$.

  • class Solution {
    public String rearrangeString(String s, char x, char y) {
        char[] t = s.toCharArray();
        int i = 0;
        for (int j = 0; j < t.length; j++) {
            if (t[j] == y) {
                char tmp = t[i];
                t[i] = t[j];
                t[j] = tmp;
                i++;
            }
        }
        return new String(t);
    }
}

  • class Solution {
public:
    string rearrangeString(string s, char x, char y) {
        int i = 0;
        for (int j = 0; j < s.size(); j++) {
            if (s[j] == y) {
                swap(s[i], s[j]);
                i++;
            }
        }
        return s;
    }
};

  • class Solution:
    def rearrangeString(self, s: str, x: str, y: str) -> str:
        t = list(s)
        i = 0
        for j, c in enumerate(t):
            if c == y:
                t[i], t[j] = c, t[i]
                i += 1
        return ''.join(t)


  • func rearrangeString(s string, x byte, y byte) string {
	t := []byte(s)
	i := 0
	for j, c := range t {
		if c == y {
			t[i], t[j] = t[j], t[i]
			i++
		}
	}
	return string(t)
}


  • function rearrangeString(s: string, x: string, y: string): string {
    const t = s.split('');
    let i = 0;
    for (let j = 0; j < t.length; j++) {
        if (t[j] === y) {
            [t[i], t[j]] = [t[j], t[i]];
            i++;
        }
    }
    return t.join('');
}

All Problems

All Solutions