514. Freedom Trail
Problem Description
In this LeetCode problem, inspired by a quest in the video game Fallout 4, you are given two strings: one represents a dial (ring
) and the other represents a keyword (key
). The ring represents a circular dial with characters engraved on its outer edge. The initial position of the dial is such that the first character starts at the 12:00 position. Your task is to rotate the dial in either a clockwise or anticlockwise direction to spell the keyword by aligning each character of the keyword at the 12:00 position and then pressing a button to confirm each character. The goal is to find the minimum number of steps required to complete this task, where each rotation (either clockwise or anticlockwise) of one place and each press of the button count as a separate step.
When rotating the ring, you may take as many steps as necessary to bring a character to the 12:00 position, and you can choose the direction that minimizes the number of steps. Each alignment followed by a press on the center button to confirm counts as a sequence necessary to spell one character of the keyword. After spelling all characters in the key, the process completes.
Flowchart Walkthrough
Let's analyze the problem on LeetCode 514, Freedom Trail, using the Flowchart. Here is how we step through the decision-making process:
Is it a graph?
- Yes: The ring of letters can be treated as a graph where each position is a node, and the edges represent moves from one position to another.
Is it a tree?
- No: The ring represents a circular structure where you can move back and forth, so there are cyclic dependencies.
Is the problem related to directed acyclic graphs (DAGs)?
- No: The problem involves navigating a circular ring, which inherently has cycles and is not acyclic.
Is the problem related to shortest paths?
- No: Although it seems related to finding a path, itās more about finding a sequence with minimum moves, rather than a shortest path in the traditional sense of graphs.
Does the problem involve connectivity?
- No: The problem is not about finding connected components or checking if parts of the graph are connected.
Does the problem have small constraints?
- Yes: The key in this problem is individual elements and their permutations or rotations, indicating a feasible approach using more exhaustive techniques.
Conclusion: According to the flowchart, if the problem involves small constraints, which can handle all permutations or arrangements exhaustively, using DFS/backtracking should be appropriate. Thus, the Depth-First Search pattern, particularly with backtracking, suits solving the Freedom Trail problem effectively.
Intuition
The intuition behind the solution is to use dynamic programming to keep track of the minimum steps required to align each character of the key
at the 12:00 position by the time we reach that character in the sequence. Our state will depend on which character from the key
we're currently looking to match and which index in the ring
is currently at the top (at the 12:00 position).
To implement this, we initialize a 2D array where each element f[i][j]
represents the minimum number of steps taken to spell the first i+1
characters of the key
with the j
-th character of ring
aligned at the top.
For the base case, we look at the first character in key
and compute the minimum steps necessary to get each occurrence of this character to the 12:00 position. This step accounts for both directions of possible rotation.
For each subsequent character in key
, we consider each position in ring
that matches the current character we would like to align and calculate the minimum steps required to reach that position from every position that matches the previous character (which we already stored in our DP array). We account for the minimum path by considering the direct distance and the wrap-around distance (the ring is circular).
The number of steps includes the actual rotations plus one step to press the button once the correct character is aligned. We repeat this process for every character in the key
.
Finally, the answer is the minimum value in the last row of our DP array since it represents the minimum steps required to align the last character of the key
.
Learn more about Depth-First Search, Breadth-First Search and Dynamic Programming patterns.
Solution Approach
The solution involves using dynamic programming (DP), a common technique for solving optimization problems where the solution can be built up by combining solutions to smaller subproblems.
-
Data Structures: We use a 2D array
f
for our DP table to keep track of the minimum steps needed, and a dictionarypos
to store the indices of each character as it appears in thering
. -
Initializing the DP Table: The DP table
f
is initialized withinf
(infinity) to indicate that we have not yet determined the minimum steps for those positions. We havem
rows in this table for each character in thekey
, andn
columns for each character in thering
. -
Base Case: We populate the first row of the DP table by calculating the minimum steps required to rotate each occurrence of the first character of the
key
to the 12:00 direction. This takes into account the minimum of a clockwise or anticlockwise rotation, which is eitherj
steps (clockwise) orn - j
steps (anticlockwise) wherej
is the index of the current character in the ring. We add 1 for pressing the button. -
DP Iteration: For each subsequent character in the
key
, we iterate through DP states from the second character to the last character. For each indexj
corresponding to the current character inkey
and each indexk
corresponding to the previous character, we updatef[i][j]
, which represents the minimum steps to reach thej-th
position of the ring to spell thei-th
character. We minimize over two possible distances: the direct step countabs(j - k)
and the wrap-around step countn - abs(j - k)
. The update equation is:f[i][j] = min(f[i][j], f[i - 1][k] + min(abs(j - k), n - abs(j - k)) + 1)
-
Final Answer: After filling in the DP table, the final answer is the minimum number of steps among all the positions that can be used to spell the last character of the
key
, which is:min(f[-1][j] for j in pos[key[-1]])
This represents taking the minimum steps across all possible indices where the last character of the
key
can be aligned.
The solution leverages the circular nature of the problem by using modular arithmetic and DP's overlapping subproblems property by storing interim solutions to avoid redundant calculations. By populating the DP table iteratively, an optimal solution to the full problem is efficiently built up from the solutions to smaller subproblems.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's consider a small example to illustrate the solution approach. Suppose we have the following ring and key:
ring = "abcde" key = "dae"
In this scenario, our goal is to align each character of key
at the 12:00 position starting with 'd', followed by 'a', and finally 'e', while counting the minimum number of steps required to do so.
Step-by-Step Walkthrough:
-
Initialization
- The
ring
"abcde" has 5 characters, and thekey
"dae" has 3 characters. - We create a 2D array
f
with dimensions 3x5, initialized withinfinity
, since ourkey
has 3 characters and ourring
has 5 characters. - We create a dictionary
pos
to map each character in thering
to the indices where they appear. For this example:pos = {'a': [0], 'b': [1], 'c': [2], 'd': [3], 'e': [4]}
- The
-
Base Case
- We fill in the first row of
f
based on the first character ofkey
, which is 'd'. - The character 'd' is at the index 3 in
ring
. To align 'd' at the top, you can rotate clockwise 3 steps, or anticlockwise 2 steps (since the ring is circular). - Since the anticlockwise rotation is shorter, we choose that path and set
f[0][3]
to 2 (for the rotations) + 1 (for pressing the button), thusf[0][3] = 3
.
- We fill in the first row of
-
DP Iteration
- Now, we consider the second character in
key
, which is 'a'. - The character 'a' is at the index 0 in
ring
, and we can reach it from the position of 'd' (index 3). - We must consider both paths: rotating clockwise 3 steps or anticlockwise 2 steps from 'd' to 'a'.
- Since we're already at 'd', the distance is 0 in this case, so we update
f[1][0]
with the value fromf[0][3] (which is 3) + 0 (for the rotation) + 1 (for pressing the button)
, thusf[1][0] = 4
.
- Now, we consider the second character in
-
Continuing with DP Iteration
- For the last character 'e' in
key
, positioned at index 4 inring
, we consider the path from 'a' at index 0. - We can rotate 4 steps clockwise or 1 step anticlockwise.
- The anticlockwise path is shorter, so we update
f[2][4]
withf[1][0] + 1 (for the rotation) + 1 (for pressing the button)
, thusf[2][4] = 6
.
- For the last character 'e' in
-
Final Answer
- The last row of array
f
now contains [inf, inf, inf, inf, 6], which represents the minimum steps required to align each position of the ring to spell the last character ofkey
. - The final answer is the minimum of these values, which is 6, at index 4.
- The last row of array
Using the above steps, we navigate the dial optimally to confirm the keyword "dae" with the minimum number of steps, 6 in this case.
Solution Implementation
1from collections import defaultdict
2from math import inf
3
4class Solution:
5
6 def findRotateSteps(self, ring: str, key: str) -> int:
7 # Initialize lengths for ring and key
8 len_key, len_ring = len(key), len(ring)
9
10 # Default dictionary to keep track of positions for each character
11 char_positions = defaultdict(list)
12
13 # Fill char_positions with indices for each character in ring
14 for index, char in enumerate(ring):
15 char_positions[char].append(index)
16
17 # Initialize the DP array with infinity
18 dp = [[inf] * len_ring for _ in range(len_key)]
19
20 # Base case for the first character in key
21 for j in char_positions[key[0]]:
22 dp[0][j] = min(j, len_ring - j) + 1
23
24 # Iterate through remaining characters in key
25 for i in range(1, len_key):
26 for j in char_positions[key[i]]:
27 for k in char_positions[key[i - 1]]:
28 # Calculate the minimum steps to rotate from character key[i-1] to key[i]
29 # Considering the circular nature of the ring
30 dp[i][j] = min(dp[i][j], dp[i - 1][k] + min(abs(j - k), len_ring - abs(j - k)) + 1)
31
32 # Return the minimum steps to spell the key last character
33 return min(dp[-1][j] for j in char_positions[key[-1]])
34
35# The Solution class can now be used with the findRotateSteps method to solve the problem.
36
1class Solution {
2 public int findRotateSteps(String ring, String key) {
3 int keyLength = key.length(); // Length of the key (sequence to spell)
4 int ringLength = ring.length(); // Length of the ring
5 // Create an array of lists to hold the positions of each character 'a'-'z' in the ring
6 List<Integer>[] pos = new List[26];
7 // Initialize each list in the array
8 Arrays.setAll(pos, k -> new ArrayList<>());
9 // Fill the positions lists with the indexes of each character in the ring
10 for (int i = 0; i < ringLength; ++i) {
11 int index = ring.charAt(i) - 'a'; // Convert char to an index 0-25
12 pos[index].add(i); // Add this character's ring position to the corresponding list
13 }
14
15 // Dynamic programming matrix where f[i][j] represents the minimum steps
16 // required to spell the key up to i-th character, ending at j-th position on the ring
17 int[][] dp = new int[keyLength][ringLength];
18 // Initialize the matrix with high values as we are looking for minimum
19 for (var row : dp) {
20 Arrays.fill(row, Integer.MAX_VALUE / 2); // Use Integer.MAX_VALUE / 2 to avoid overflow
21 }
22 // Initialize the first row of the dp matrix based on the first character of the key
23 for (int j : pos[key.charAt(0) - 'a']) {
24 dp[0][j] = Math.min(j, ringLength - j) + 1;
25 }
26 // Populate the matrix using previously calculated entries
27 for (int i = 1; i < keyLength; ++i) {
28 for (int j : pos[key.charAt(i) - 'a']) {
29 for (int k : pos[key.charAt(i - 1) - 'a']) {
30 // The current state is the minimum of the current state and
31 // possible previous state plus the distance between k and j plus one for the button press
32 dp[i][j] = Math.min(
33 dp[i][j], dp[i - 1][k] + Math.min(Math.abs(j - k), ringLength - Math.abs(j - k)) + 1);
34 }
35 }
36 }
37 // Initialize answer to a high value to find the minimum
38 int answer = Integer.MAX_VALUE / 2;
39 // Iterate through the final characters positions to find the minimum steps required
40 for (int j : pos[key.charAt(keyLength - 1) - 'a']) {
41 answer = Math.min(answer, dp[keyLength - 1][j]);
42 }
43 // Return the minimum steps found
44 return answer;
45 }
46}
47
1#include <vector>
2#include <string>
3#include <cstring>
4#include <algorithm>
5
6using namespace std;
7
8class Solution {
9public:
10 int findRotateSteps(string ring, string key) {
11 int keyLength = key.size(); // Length of the key
12 int ringLength = ring.size(); // Length of the ring
13 vector<int> position[26]; // Array of vectors to hold the positions of each character
14
15 // Populate the position array with the indices of each character in the ring
16 for (int i = 0; i < ringLength; ++i) {
17 position[ring[i] - 'a'].push_back(i);
18 }
19
20 // Initialize the dynamic programming table, f, with infinity
21 int dpTable[keyLength][ringLength];
22 memset(dpTable, 0x3f, sizeof(dpTable));
23
24 // Base case: fill in the first row of the dynamic programming table
25 for (int index : position[key[0] - 'a']) {
26 dpTable[0][index] = min(index, ringLength - index) + 1;
27 }
28
29 // Fill in the remainder of the dp table
30 for (int i = 1; i < keyLength; ++i) {
31 for (int j : position[key[i] - 'a']) {
32 for (int k : position[key[i - 1] - 'a']) {
33 int stepDiff = min(abs(j - k), ringLength - abs(j - k)) + 1; // Calculate the minimum steps
34 dpTable[i][j] = min(dpTable[i][j], dpTable[i - 1][k] + stepDiff);
35 }
36 }
37 }
38
39 // Find the minimum steps needed to spell the last character of the key
40 int minSteps = INT_MAX;
41 for (int index : position[key[keyLength - 1] - 'a']) {
42 minSteps = min(minSteps, dpTable[keyLength - 1][index]);
43 }
44
45 // Return the minimum steps to spell all characters in the key
46 return minSteps;
47 }
48};
49
1function findRotateSteps(ring: string, key: string): number {
2 const keyLength: number = key.length; // Length of the key
3 const ringLength: number = ring.length; // Length of the ring
4 const position: number[][] = Array.from({length: 26}, () => []); // Array of arrays to hold positions of each character
5
6 // Populate the 'position' array with the indices of each character in the ring
7 for (let i = 0; i < ringLength; ++i) {
8 position[ring.charCodeAt(i) - 'a'.charCodeAt(0)].push(i);
9 }
10
11 // Initialize the dynamic programming table with high values
12 const dpTable = Array.from({length: keyLength}, () => Array(ringLength).fill(Number.MAX_SAFE_INTEGER));
13
14 // Base case: fill in the first row of the dynamic programming table
15 for (const index of position[key.charCodeAt(0) - 'a'.charCodeAt(0)]) {
16 dpTable[0][index] = Math.min(index, ringLength - index) + 1;
17 }
18
19 // Fill in the remainder of the dp table
20 for (let i = 1; i < keyLength; ++i) {
21 for (const j of position[key.charCodeAt(i) - 'a'.charCodeAt(0)]) {
22 for (const k of position[key.charCodeAt(i - 1) - 'a'.charCodeAt(0)]) {
23 const stepDiff = Math.min(Math.abs(j - k), ringLength - Math.abs(j - k)) + 1; // Calculate the minimum steps
24 dpTable[i][j] = Math.min(dpTable[i][j], dpTable[i - 1][k] + stepDiff);
25 }
26 }
27 }
28
29 // Find the minimum steps needed to spell the last character of the key
30 let minSteps = Number.MAX_SAFE_INTEGER;
31 for (const index of position[key.charCodeAt(keyLength - 1) - 'a'.charCodeAt(0)]) {
32 minSteps = Math.min(minSteps, dpTable[keyLength - 1][index]);
33 }
34
35 // Return the minimum steps to spell all characters in the key
36 return minSteps;
37}
38
Time and Space Complexity
Time Complexity
The time complexity of this dynamic programming solution can be analyzed based on the nested loops present in the algorithm:
-
The first loop is iterating over the characters in the key string, which has a length of
m
. Therefore, it contributes O(m) to the time complexity. -
The second and third loops are iterating over the positions of characters in the
ring
that match the current and previous characters of thekey
. In the worst case, it's possible that each character in the ring matches the key characters, hence both these loops could iterate up ton
times, wheren
is the length of thering
. -
The innermost statement that executes within the nested loops does constant work (calculating minimums and arithmetic operations), therefore each execution contributes O(1).
By multiplying these together, the overall worst-case time complexity is O(m * n^2).
Space Complexity
The space complexity is determined by the space required to store the dynamic programming table f
and the position map pos
:
-
The DP table
f
is anm
byn
matrix wherem
is the length of thekey
andn
is the length of thering
. Thus, the space complexity contribution for the dynamic programming table is O(m * n). -
The
pos
dictionary can hold at mostn
positions for each unique character in thering
. In the worst case, where all characters are unique, it could storen
positions forn
different characters. Thus, its contribution is O(n^2) in this scenario.
However, since the ring consists of characters, and even considering an extended character set, the number of unique characters would not realistically scale with n
. Therefore, many consider the space complexity for the pos
dictionary to be O(n) because the number of unique keys (characters) in the dictionary is a constant factor not dependent on the input size.
Taking the larger space complexity between these two, the overall space complexity is O(m * n).
Learn more about how to find time and space complexity quickly using problem constraints.
You are given an array of intervals where intervals[i] = [start_i, end_i]
represent the start and end of the ith
interval. You need to merge all overlapping intervals and return an array of the non-overlapping intervals that cover all the intervals in the input.
Recommended Readings
https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS
https algomonster s3 us east 2 amazonaws com cover_photos bfs svg Breadth First Search on Trees Hopefully by this time you've drunk enough DFS Kool Aid to understand its immense power and seen enough visualization to create a call stack in your mind Now let me introduce the companion spell
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
Want a Structured Path to Master System Design Too? Donāt Miss This!