How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at DoorDash.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at DoorDash during technical interviews.

Can two names match with ≤2 swaps? | DoorDash Coding Question

Can two names match with ≤2 swaps?

Company: DoorDash

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

You are given two restaurant names represented as strings `s` and `t` of equal length (same character set, case-sensitive). In one operation, you may **swap** any two characters in `s` (i.e., pick indices `i` and `j` and exchange `s[i]` and `s[j]`). You may perform **at most 2 swaps**. Return `true` if you can transform `s` into exactly `t` using at most 2 swaps; otherwise return `false`. Constraints (reasonable assumptions): - `1 <= n = s.length = t.length <= 2e5` - Characters are ASCII letters (or lowercase English letters). Example: - `s = "abca"`, `t = "aabc"` -> `true` (swap indices 1 and 3 to get "aabc") - `s = "abcd"`, `t = "badc"` -> `true` (swap (0,1) then swap (2,3)) - `s = "abcd"`, `t = "abdc"` -> `true` (one swap) - `s = "abcd"`, `t = "abdd"` -> `false` (different multiset of characters)

Quick Answer: This question evaluates string manipulation and combinatorial reasoning skills, focusing on character multisets, permutations, and the implications of a bounded number of swap operations.

You are given two restaurant names represented as strings s and t. In one operation, you may choose any two indices in s and swap the characters at those indices. Return True if s can be transformed into exactly t using at most 2 swaps. Otherwise, return False. The comparison is case-sensitive.

Constraints

1 <= len(s) = len(t) <= 200000
s and t contain ASCII letters or lowercase English letters
Comparison is case-sensitive

Examples

Input: ("abca", "aabc")

Expected Output: True

Explanation: Swap indices 1 and 3 to get "aacb", then swap indices 2 and 3 to get "aabc".

Input: ("abcd", "badc")

Expected Output: True

Explanation: Swap indices 0 and 1 to get "bacd", then swap indices 2 and 3 to get "badc".

Input: ("abcd", "abdc")

Expected Output: True

Explanation: One swap of indices 2 and 3 transforms s into t.

Input: ("abcd", "abdd")

Expected Output: False

Explanation: The two strings do not contain the same multiset of characters, so no swaps can make them equal.

Input: ("abcd", "bcda")

Expected Output: False

Explanation: All four positions mismatch, but this is a 4-cycle and requires 3 swaps, which is more than allowed.

Input: ("abcde", "eabcd")

Expected Output: False

Explanation: There are 5 mismatched positions. Two swaps can affect at most 4 positions.

Input: ("same", "same")

Expected Output: True

Explanation: The strings are already equal, so 0 swaps are needed.

Input: ("Aa", "aA")

Expected Output: True

Explanation: The comparison is case-sensitive, and swapping the two characters transforms s into t.

Input: ("a", "b")

Expected Output: False

Explanation: A single-character string cannot be changed by swapping, and the characters differ.

Hints

A single swap can only change the characters at two positions. How many mismatched positions can two swaps affect at most?
Once you know the mismatched positions, there are only a few possible swaps worth trying.

Quick Overview

This question evaluates string manipulation and combinatorial reasoning skills, focusing on character multisets, permutations, and the implications of a bounded number of swap operations.