Skip to content

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\).

1
2
3
4
5
6
7
8
9
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)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
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);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
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)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
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('');
}

Comments