Jobs

Interviews

Discussions

Swap Adjacent in LR String

Medium

Asked by:

13 views

Topics:

StringsTwo Pointers

In a string composed of 'L', 'R', and 'X' characters, like "RXXLRXRXL", a move consists of either replacing one occurrence of "XL" with "LX", or replacing one occurrence of "RX" with "XR". Given the starting string start and the ending string result, return True if and only if there exists a sequence of moves to transform start to result.

Example 1:

Input: start = "RXXLRXRXL", result = "XRLXXRRLX"
Output: true
Explanation: We can transform start to result following these steps:
RXXLRXRXL ->
XRXLRXRXL ->
XRLXRXRXL ->
XRLXXRRXL ->
XRLXXRRLX

Example 2:

Input: start = "X", result = "L"
Output: false

Constraints:

1 <= start.length <= 10⁴
start.length == result.length
Both start and result will only consist of characters in 'L', 'R', and 'X'.

Try coding it in LeetCode

Swap Adjacent in LR String

Medium

Asked by:

13 views

Topics:

StringsTwo Pointers

Example 1:

Input: start = "RXXLRXRXL", result = "XRLXXRRLX"
Output: true
Explanation: We can transform start to result following these steps:
RXXLRXRXL ->
XRXLRXRXL ->
XRLXRXRXL ->
XRLXXRRXL ->
XRLXXRRLX

Example 2:

Input: start = "X", result = "L"
Output: false

Constraints:

1 <= start.length <= 10⁴
start.length == result.length
Both start and result will only consist of characters in 'L', 'R', and 'X'.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the input string `start` and `end` contain characters other than 'L', 'R', and 'X'?
If it's impossible to transform `start` into `end`, should I return `false` or throw an exception?
Are the lengths of the `start` and `end` strings always equal, and are they ever empty?
For 'L' characters, can they only move to the left (swap with an 'X' on their left), and similarly, can 'R' characters only move to the right (swap with an 'X' on their right)?
If there are multiple valid sequences of swaps that can transform `start` into `end`, is any valid transformation acceptable, or are there specific constraints on which swaps are allowed?

Brute Force Solution

Approach

The brute force method for this problem involves exploring all possible arrangements of characters in the starting string. We systematically try moving the 'L's and 'R's around within the string, checking each arrangement to see if it matches the target string.

Here's how the algorithm would work step-by-step:

Start by considering the initial string.
Look for an 'L' that can potentially move left (an 'L' followed by an 'X'). Try swapping them, creating a new string.
Also, look for an 'R' that can potentially move right (an 'R' followed by an 'X'). Try swapping them, creating another new string.
Now, for each of these new strings, repeat the process: try moving 'L's left and 'R's right to generate even more strings.
Keep doing this, creating more and more strings by swapping 'L's and 'R's.
As you generate each new string, compare it to the target string.
If you ever find a string that matches the target, then you know it's possible to transform the start string into the target string.
If you've tried every single possible move and haven't found the target string, then it's not possible to transform the start string into the target string.

Code Implementation

def can_transform_brute_force(start_string, end_string):
    possible_states = {start_string}
    visited_states = {start_string}

    while possible_states:
        current_state = possible_states.pop()

        if current_state == end_string:
            return True

        next_states = generate_next_states(current_state)

        for next_state in next_states:
            # Avoid infinite loops by not revisiting states
            if next_state not in visited_states:
                possible_states.add(next_state)
                visited_states.add(next_state)

    return False

def generate_next_states(current_string):
    next_states = []
    string_length = len(current_string)

    for index in range(string_length - 1):
        # L can only move left into an X
        if current_string[index] == 'L' and current_string[index + 1] == 'X':
            next_states.append(current_string[:index] + 'X' + 'L' + current_string[index + 2:])

        # R can only move right into an X
        if current_string[index] == 'R' and current_string[index + 1] == 'X':
            next_states.append(current_string[:index] + 'X' + 'R' + current_string[index + 2:])

    return next_states

Big(O) Analysis

Time Complexity

O((n+m)!) – Let n be the number of 'L's and m be the number of 'R's in the string (input size). In the worst-case scenario, we explore all possible permutations of moving 'L's to the left and 'R's to the right amongst the 'X's. Each 'L' can potentially move past a certain number of 'X's, and similarly for 'R's. This leads to a tree-like exploration of possible arrangements. The number of possible arrangements grows factorially with the number of 'L's and 'R's, resulting in an exponential number of states to explore. Therefore, the time complexity is proportional to the factorial of the sum of 'L's and 'R's i.e. (n+m)!, since we are exploring all possible permutations. Comparing each generated string to the target takes O(length of the string), which doesn't change the overall factorial nature.

Space Complexity

O(N!) – The brute force approach explores all possible string arrangements resulting from swapping 'L's and 'R's with adjacent 'X's. In the worst-case scenario, the algorithm could potentially generate all permutations of the string, where N is the length of the start string. This would require storing a potentially exponential number of strings (up to N!) in a queue or similar data structure to track the strings to explore. Therefore, the auxiliary space complexity is O(N!).

Optimal Solution

Approach

The core idea is to validate if the starting string can be transformed into the ending string through allowed swaps. We can only move 'R' to the right and 'L' to the left. The key insight is that the relative order of 'R's and 'L's must remain the same, but their positions might shift due to the 'X's.

Here's how the algorithm would work step-by-step:

First, ignore all the 'X's in both strings and check if the remaining sequences of 'R's and 'L's are identical. If they aren't, the transformation is impossible.
Next, go character by character in the start string. If you find an 'R', check if its position is to the left of the corresponding 'R' in the end string. If it is, this is not a valid move as 'R' can only move right.
Similarly, if you find an 'L', check if its position is to the right of the corresponding 'L' in the end string. If it is, this is not a valid move as 'L' can only move left.
If all 'R's are to the left or at the same position as their corresponding 'R's in the end string, and all 'L's are to the right or at the same position as their corresponding 'L's in the end string, then the transformation is possible.

Code Implementation

def can_transform(start_string, end_string):
    start_without_x = start_string.replace('X', '')
    end_without_x = end_string.replace('X', '')

    if start_without_x != end_without_x:
        return False

    start_index = 0
    end_index = 0

    while start_index < len(start_string) and end_index < len(end_string):
        if start_string[start_index] == 'X':
            start_index += 1
            continue
        if end_string[end_index] == 'X':
            end_index += 1
            continue

        if start_string[start_index] == 'R':
            # R can only move to the right
            if end_string[end_index] == 'R':
                if start_index > end_index:
                    return False
            
        elif start_string[start_index] == 'L':
            # L can only move to the left
            if end_string[end_index] == 'L':
                if start_index < end_index:
                    return False

        start_index += 1
        end_index += 1

    return True

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through both the start and end strings, each of length n, a maximum of once. The first step filters both strings to remove 'X' characters, which takes O(n) time for each string. The second step iterates through the filtered strings comparing the positions of 'R' and 'L' which is also bounded by O(n) where n is the length of the original strings. Therefore, the overall time complexity is O(n).

Space Complexity

O(1) – The algorithm iterates through the input strings 'start' and 'end' using index variables. It compares characters at corresponding positions and determines if the transformation is valid based on the relative positions of 'R's and 'L's. The plain English solution does not explicitly create any auxiliary data structures like lists, maps, or sets to store intermediate results, and the number of variables used does not scale with the input size N (where N is the length of the input strings). Therefore, the auxiliary space complexity is constant.

Edge Cases

Case	How to Handle
start or end string is null or empty	Return true if both are null or empty, false if only one is, and continue processing otherwise assuming empty strings are valid states.
start and end strings have different lengths	Return false immediately as the number of characters must be equal for swaps to lead to valid state transformations.
start and end strings have different counts of 'L' and 'R' characters	Return false immediately because 'L' and 'R' characters can only move, not disappear or be created.
An 'L' in the start string is to the right of an 'L' in the end string at the same non-'X' index.	Return false because 'L' characters can only move left.
An 'R' in the start string is to the left of an 'R' in the end string at the same non-'X' index.	Return false because 'R' characters can only move right.
Very long strings exceeding typical memory constraints.	Consider processing the strings in chunks, comparing substrings and tracking the relative movement of 'L' and 'R' within those chunks.
Start and end strings are identical, but only contain 'X' characters.	Return true immediately as no moves are needed.
The middle part of the string contains only 'X' and the left part of start and end contain R, while right part contains L.	Return true if all R are on the left and all L are on the right, separated by X, according to the start and end condition.

start or end string is null or empty

How to Handle:

Return true if both are null or empty, false if only one is, and continue processing otherwise assuming empty strings are valid states.

start and end strings have different lengths

How to Handle:

Return false immediately as the number of characters must be equal for swaps to lead to valid state transformations.

start and end strings have different counts of 'L' and 'R' characters

How to Handle:

Return false immediately because 'L' and 'R' characters can only move, not disappear or be created.

An 'L' in the start string is to the right of an 'L' in the end string at the same non-'X' index.

How to Handle:

Return false because 'L' characters can only move left.

An 'R' in the start string is to the left of an 'R' in the end string at the same non-'X' index.

How to Handle:

Return false because 'R' characters can only move right.

Very long strings exceeding typical memory constraints.

How to Handle:

Consider processing the strings in chunks, comparing substrings and tracking the relative movement of 'L' and 'R' within those chunks.

Start and end strings are identical, but only contain 'X' characters.

How to Handle:

Return true immediately as no moves are needed.

The middle part of the string contains only 'X' and the left part of start and end contain R, while right part contains L.

How to Handle:

Return true if all R are on the left and all L are on the right, separated by X, according to the start and end condition.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the input string `start` and `end` contain characters other than 'L', 'R', and 'X'?
If it's impossible to transform `start` into `end`, should I return `false` or throw an exception?
Are the lengths of the `start` and `end` strings always equal, and are they ever empty?
For 'L' characters, can they only move to the left (swap with an 'X' on their left), and similarly, can 'R' characters only move to the right (swap with an 'X' on their right)?
If there are multiple valid sequences of swaps that can transform `start` into `end`, is any valid transformation acceptable, or are there specific constraints on which swaps are allowed?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start by considering the initial string.
Look for an 'L' that can potentially move left (an 'L' followed by an 'X'). Try swapping them, creating a new string.
Also, look for an 'R' that can potentially move right (an 'R' followed by an 'X'). Try swapping them, creating another new string.
Now, for each of these new strings, repeat the process: try moving 'L's left and 'R's right to generate even more strings.
Keep doing this, creating more and more strings by swapping 'L's and 'R's.
As you generate each new string, compare it to the target string.
If you ever find a string that matches the target, then you know it's possible to transform the start string into the target string.
If you've tried every single possible move and haven't found the target string, then it's not possible to transform the start string into the target string.

Code Implementation

def can_transform_brute_force(start_string, end_string):
    possible_states = {start_string}
    visited_states = {start_string}

    while possible_states:
        current_state = possible_states.pop()

        if current_state == end_string:
            return True

        next_states = generate_next_states(current_state)

        for next_state in next_states:
            # Avoid infinite loops by not revisiting states
            if next_state not in visited_states:
                possible_states.add(next_state)
                visited_states.add(next_state)

    return False

def generate_next_states(current_string):
    next_states = []
    string_length = len(current_string)

    for index in range(string_length - 1):
        # L can only move left into an X
        if current_string[index] == 'L' and current_string[index + 1] == 'X':
            next_states.append(current_string[:index] + 'X' + 'L' + current_string[index + 2:])

        # R can only move right into an X
        if current_string[index] == 'R' and current_string[index + 1] == 'X':
            next_states.append(current_string[:index] + 'X' + 'R' + current_string[index + 2:])

    return next_states

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, ignore all the 'X's in both strings and check if the remaining sequences of 'R's and 'L's are identical. If they aren't, the transformation is impossible.
Next, go character by character in the start string. If you find an 'R', check if its position is to the left of the corresponding 'R' in the end string. If it is, this is not a valid move as 'R' can only move right.
Similarly, if you find an 'L', check if its position is to the right of the corresponding 'L' in the end string. If it is, this is not a valid move as 'L' can only move left.
If all 'R's are to the left or at the same position as their corresponding 'R's in the end string, and all 'L's are to the right or at the same position as their corresponding 'L's in the end string, then the transformation is possible.

Code Implementation

def can_transform(start_string, end_string):
    start_without_x = start_string.replace('X', '')
    end_without_x = end_string.replace('X', '')

    if start_without_x != end_without_x:
        return False

    start_index = 0
    end_index = 0

    while start_index < len(start_string) and end_index < len(end_string):
        if start_string[start_index] == 'X':
            start_index += 1
            continue
        if end_string[end_index] == 'X':
            end_index += 1
            continue

        if start_string[start_index] == 'R':
            # R can only move to the right
            if end_string[end_index] == 'R':
                if start_index > end_index:
                    return False
            
        elif start_string[start_index] == 'L':
            # L can only move to the left
            if end_string[end_index] == 'L':
                if start_index < end_index:
                    return False

        start_index += 1
        end_index += 1

    return True

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
start or end string is null or empty	Return true if both are null or empty, false if only one is, and continue processing otherwise assuming empty strings are valid states.
start and end strings have different lengths	Return false immediately as the number of characters must be equal for swaps to lead to valid state transformations.
start and end strings have different counts of 'L' and 'R' characters	Return false immediately because 'L' and 'R' characters can only move, not disappear or be created.
An 'L' in the start string is to the right of an 'L' in the end string at the same non-'X' index.	Return false because 'L' characters can only move left.
An 'R' in the start string is to the left of an 'R' in the end string at the same non-'X' index.	Return false because 'R' characters can only move right.
Very long strings exceeding typical memory constraints.	Consider processing the strings in chunks, comparing substrings and tracking the relative movement of 'L' and 'R' within those chunks.
Start and end strings are identical, but only contain 'X' characters.	Return true immediately as no moves are needed.
The middle part of the string contains only 'X' and the left part of start and end contain R, while right part contains L.	Return true if all R are on the left and all L are on the right, separated by X, according to the start and end condition.

start or end string is null or empty

How to Handle:

Return true if both are null or empty, false if only one is, and continue processing otherwise assuming empty strings are valid states.

start and end strings have different lengths

How to Handle:

Return false immediately as the number of characters must be equal for swaps to lead to valid state transformations.

start and end strings have different counts of 'L' and 'R' characters

How to Handle:

Return false immediately because 'L' and 'R' characters can only move, not disappear or be created.

An 'L' in the start string is to the right of an 'L' in the end string at the same non-'X' index.

How to Handle:

Return false because 'L' characters can only move left.

An 'R' in the start string is to the left of an 'R' in the end string at the same non-'X' index.

How to Handle:

Return false because 'R' characters can only move right.

Very long strings exceeding typical memory constraints.

How to Handle:

Consider processing the strings in chunks, comparing substrings and tracking the relative movement of 'L' and 'R' within those chunks.

Start and end strings are identical, but only contain 'X' characters.

How to Handle:

Return true immediately as no moves are needed.

The middle part of the string contains only 'X' and the left part of start and end contain R, while right part contains L.

How to Handle:

Return true if all R are on the left and all L are on the right, separated by X, according to the start and end condition.