snippetModerate
How to check if two strings are permutations of each other using O(1) additional space?
Viewed 0 times
spaceeachareothertwousinghowcheckstringsadditional
Problem
Given two strings how can you check if they are a permutation of each other using O(1) space? Modifying the strings is not allowed in any way.
Note: O(1) space in relation to both the string length AND the size of the alphabet.
Note: O(1) space in relation to both the string length AND the size of the alphabet.
Solution
Denote the arrays by $A,B$, and suppose they are of length $n$.
Suppose first that the values in each array are distinct. Here is an algorithm that uses $O(1)$ space:
-
Compute the minimum values of both arrays, and check that they are identical.
-
Compute the second minimum values of both arrays, and check that they are identical.
-
And so on.
Computing the minimum value of an array clearly uses $O(1)$ space. Given the $k$th smallest element, we can find the $(k+1)$st smallest element by finding the minimal value larger than the $k$th smallest element (here we use the fact that all elements are distinct).
When elements are allowed to repeat, we modify the algorithm as follows:
-
Compute the minimum values $m_{A,1},m_{B,1}$ of both arrays, count how many times each appear, and verify the $m_{A,1} = m_{B,1}$ and that the counts are identical.
-
Compute the minimum values $m_{A,2},m_{B,2}$ larger than $m_{A,1},m_{B,1}$ in the two arrays (respectively), and count how many times each appear. Verify that $m_{A,2} = m_{B,2}$, and that the counts are identical.
-
And so on.
Suppose first that the values in each array are distinct. Here is an algorithm that uses $O(1)$ space:
-
Compute the minimum values of both arrays, and check that they are identical.
-
Compute the second minimum values of both arrays, and check that they are identical.
-
And so on.
Computing the minimum value of an array clearly uses $O(1)$ space. Given the $k$th smallest element, we can find the $(k+1)$st smallest element by finding the minimal value larger than the $k$th smallest element (here we use the fact that all elements are distinct).
When elements are allowed to repeat, we modify the algorithm as follows:
-
Compute the minimum values $m_{A,1},m_{B,1}$ of both arrays, count how many times each appear, and verify the $m_{A,1} = m_{B,1}$ and that the counts are identical.
-
Compute the minimum values $m_{A,2},m_{B,2}$ larger than $m_{A,1},m_{B,1}$ in the two arrays (respectively), and count how many times each appear. Verify that $m_{A,2} = m_{B,2}$, and that the counts are identical.
-
And so on.
Context
StackExchange Computer Science Q#76474, answer score: 12
Revisions (0)
No revisions yet.