Update special-binary-string.py

kamyu104 · web-flow · commit 2f769ba0f6b8 · 2018-01-09T13:37:19.000+08:00
diff --git a/Python/special-binary-string.py b/Python/special-binary-string.py
@@ -1,7 +1,30 @@
 # Time:  f(n) = k * f(n/k) + n/k * klogk <= O(logn * nlogk) <= O(n^2)
 #        n is the length of S, k is the max number of special strings in each depth
 # Space: O(n)
-    
+
+# Special binary strings are binary strings with the following two properties:
+#
+# The number of 0's is equal to the number of 1's.
+# Every prefix of the binary string has at least as many 1's as 0's.
+# Given a special string S, a move consists of choosing two consecutive, non-empty,
+# special substrings of S, and swapping them.
+# (Two strings are consecutive if the last character of the first string is 
+# exactly one index before the first character of the second string.)
+#
+# At the end of any number of moves, what is the lexicographically largest resulting string possible?
+#
+# Example 1:
+# Input: S = "11011000"
+# Output: "11100100"
+#
+# Explanation:
+# The strings "10" [occuring at S[1]] and "1100" [at S[3]] are swapped.
+# This is the lexicographically largest string possible after some number of swaps.
+#
+# Note:
+# - S has length at most 50.
+# - S is guaranteed to be a special binary string as defined above.
+
 class Solution(object):
     def makeLargestSpecial(self, S):
         """
