Since the array is circular, I iterate through each element and compute the absolute difference between every pair of adjacent elements, including the last and the first. I keep track of the maximum difference encountered during this iteration.
class Solution:To solve this, I first count the frequency of each character in the string using a frequency map. Then, I look for characters that have odd frequencies and track the maximum among them, since I'm trying to maximize the result. Simultaneously, I look for characters that have even frequencies and track the minimum among them, because subtracting a smaller even count gives a larger difference. Finally, I return the difference between the maximum odd frequency and the minimum even frequency.
class Solution:I thought of the numbers as forming a tree — where each node represents a number, and its children are formed by appending digits 0 through 9. I used a pre-order traversal approach to explore this virtual tree. I started with 1, and at each step, I either moved deeper by multiplying the number by 10 or incremented to the next number. If the current number ended with 9 or the next number exceeded n, I backtracked by dividing the number until I found a valid next sibling.
class Solution:
def lexicalOrder(self, n: int) -> List[int]:I iterate through the string and use a stack to maintain the current characters. For each non-'*' character, I push it onto the stack. When I encounter a '*', I scan the stack to find and remove the smallest non-'*' character to its left, as required by the problem. This ensures the resulting string is lexicographically smallest after all '*' removals. Finally, I join and return the remaining characters in the stack. This kept on failing the first test case "aaba*" for some reason so editiorial sharps
To get the lexicographically smallest string that can be written on paper, I simulate the robot's operations using a monotonic greedy approach. As I traverse the input string s, I push each character into a stack t (representing the robot's hand). Before moving to the next character, I decide whether to pop from the stack and write to the result based on whether the top of the stack is less than or equal to the smallest character remaining in s. To do this efficiently, I precompute an array min_char where min_char[i] stores the smallest character from s[i] to the end. At each step, if the top of the stack is smaller than or equal to the future minimum, I pop it and add it to the result.
class Solution:I use a Union-Find data structure to maintain equivalence classes between characters from s1 and s2. For each pair (s1[i], s2[i]), I unify their groups such that the representative (or parent) of the group is always the smallest character lexicographically. Once all equivalence relations are processed, I iterate over baseStr, and for each character, I replace it with its group's representative — which ensures that I get the lexicographically smallest equivalent string.
class Solution:
def smallestEquivalentString(self, s1: str, s2: str, baseStr: str) -> str:I generated all possible ways to split the input string into numFriends non-empty parts by using recursion with memoization. For each valid split, I collected all the substrings generated and stored them. After exploring all valid splits, I found the lexicographically largest string among all the substrings that were ever created in any round. This first approach took a lot of memory (got an MLE (Memory Limit Exceeded)). Tried other methods like dfs and the likes but I still got TLE or MLE. I gave in and used the editorial.
