New Problem Solution -"Lexicographically Smallest String After Applying Operations"

haoel · haoel · commit ed3c20224bcb · 2021-03-24T21:05:47.000+08:00
diff --git a/README.md b/README.md
@@ -50,6 +50,7 @@ LeetCode
 |1734|[Decode XORed Permutation](https://leetcode.com/problems/decode-xored-permutation/) | [C++](./algorithms/cpp/decodeXORedPermutation/DecodeXoredPermutation.cpp)|Medium|
 |1733|[Minimum Number of People to Teach](https://leetcode.com/problems/minimum-number-of-people-to-teach/) | [C++](./algorithms/cpp/minimumNumberOfPeopleToTeach/MinimumNumberOfPeopleToTeach.cpp)|Medium|
 |1732|[Find the Highest Altitude](https://leetcode.com/problems/find-the-highest-altitude/) | [C++](./algorithms/cpp/findTheHighestAltitude/FindTheHighestAltitude.cpp)|Easy|
+|1625|[Lexicographically Smallest String After Applying Operations](https://leetcode.com/problems/lexicographically-smallest-string-after-applying-operations/) | [C++](./algorithms/cpp/lexicographicallySmallestStringAfterApplyingOperations/LexicographicallySmallestStringAfterApplyingOperations.cpp)|Medium|
 |1624|[Largest Substring Between Two Equal Characters](https://leetcode.com/problems/largest-substring-between-two-equal-characters/) | [C++](./algorithms/cpp/largestSubstringBetweenTwoEqualCharacters/LargestSubstringBetweenTwoEqualCharacters.cpp)|Easy|
 |1605|[Find Valid Matrix Given Row and Column Sums](https://leetcode.com/problems/find-valid-matrix-given-row-and-column-sums/) | [C++](./algorithms/cpp/FindValidMatrixGivenRowAndColumnSums/FindValidMatrixGivenRowAndColumnSums.cpp)|Medium|
 |1573|[Number of Ways to Split a String](https://leetcode.com/problems/number-of-ways-to-split-a-string/) | [C++](./algorithms/cpp/NumberOfWaysToSplitString/NumberOfWaysToSplitString.cpp)|Medium|
diff --git a/algorithms/cpp/lexicographicallySmallestStringAfterApplyingOperations/LexicographicallySmallestStringAfterApplyingOperations.cpp b/algorithms/cpp/lexicographicallySmallestStringAfterApplyingOperations/LexicographicallySmallestStringAfterApplyingOperations.cpp
@@ -0,0 +1,106 @@
+// Source : https://leetcode.com/problems/lexicographically-smallest-string-after-applying-operations/
+// Author : Hao Chen
+// Date   : 2021-03-24
+
+/***************************************************************************************************** 
+ *
+ * You are given a string s of even length consisting of digits from 0 to 9, and two integers a and b.
+ * 
+ * You can apply either of the following two operations any number of times and in any order on s:
+ * 
+ * 	Add a to all odd indices of s (0-indexed). Digits post 9 are cycled back to 0. For example, 
+ * if s = "3456" and a = 5, s becomes "3951".
+ * 	Rotate s to the right by b positions. For example, if s = "3456" and b = 1, s becomes 
+ * "6345".
+ * 
+ * Return the lexicographically smallest string you can obtain by applying the above operations any 
+ * number of times on s.
+ * 
+ * A string a is lexicographically smaller than a string b (of the same length) if in the first 
+ * position where a and b differ, string a has a letter that appears earlier in the alphabet than the 
+ * corresponding letter in b. For example, "0158" is lexicographically smaller than "0190" because the 
+ * first position they differ is at the third letter, and '5' comes before '9'.
+ * 
+ * Example 1:
+ * 
+ * Input: s = "5525", a = 9, b = 2
+ * Output: "2050"
+ * Explanation: We can apply the following operations:
+ * Start:  "5525"
+ * Rotate: "2555"
+ * Add:    "2454"
+ * Add:    "2353"
+ * Rotate: "5323"
+ * Add:    "5222"
+ * ​​​​​​​Add:    "5121"
+ * ​​​​​​​Rotate: "2151"
+ * ​​​​​​​Add:    "2050"​​​​​​​​​​​​
+ * There is no way to obtain a string that is lexicographically smaller then "2050".
+ * 
+ * Example 2:
+ * 
+ * Input: s = "74", a = 5, b = 1
+ * Output: "24"
+ * Explanation: We can apply the following operations:
+ * Start:  "74"
+ * Rotate: "47"
+ * ​​​​​​​Add:    "42"
+ * ​​​​​​​Rotate: "24"​​​​​​​​​​​​
+ * There is no way to obtain a string that is lexicographically smaller then "24".
+ * 
+ * Example 3:
+ * 
+ * Input: s = "0011", a = 4, b = 2
+ * Output: "0011"
+ * Explanation: There are no sequence of operations that will give us a lexicographically smaller 
+ * string than "0011".
+ * 
+ * Example 4:
+ * 
+ * Input: s = "43987654", a = 7, b = 3
+ * Output: "00553311"
+ * 
+ * Constraints:
+ * 
+ * 	2 <= s.length <= 100
+ * 	s.length is even.
+ * 	s consists of digits from 0 to 9 only.
+ * 	1 <= a <= 9
+ * 	1 <= b <= s.length - 1
+ ******************************************************************************************************/
+
+class Solution {
+private:
+    unordered_map<string, bool> processed;
+    void rotate_str(string& s, int n) {
+        std::rotate(s.begin(), s.begin()+n, s.end());
+    }
+    void add_str(string& s, int n) {
+        for(int i=1; i<s.size(); i+=2) {
+            s[i] = (s[i] -'0' + n) % 10 +'0';
+        }
+    }
+public:
+    string findLexSmallestString(string s, int a, int b) {
+        string result = s;
+        dfs(s, a, b, result);
+        return result;
+    }
+    
+    void dfs(string& s, int a, int b, string& result) {
+        
+        if (processed.find(s) != processed.end()) return;
+        processed[s] = true;
+        
+        if (s < result) result = s;
+        
+        string str = s;
+        rotate_str(str, b); 
+        dfs(str, a, b, result);
+        
+        str = s;
+        add_str(str, a); 
+        dfs(str, a, b, result);
+        
+    }
+};
