Given a pattern containing only I's and D's. I for increasing and D for decreasing.
Devise an algorithm to print the minimum number following that pattern.
Digits from 1-9 and digits can't repeat.
 
Example 1:
Input:
D
Output:
21
Explanation:
D is meant for decreasing,
So we choose the minimum number
among 21,31,54,87,etc.
 
Example 2:
Input:
IIDDD
Output:
126543
Explanation:
Above example is self- explanatory,
1 < 2 < 6 > 5 > 4 > 3
  I - I - D - D - D
 
 
Your Task:
You don't need to read input or print anything. Your task is to complete the function printMinNumberForPattern() which takes the string S and returns a string containing the minimum number following the valid pattern.
 
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
 
Constraints:
1 ≤ Length of String ≤ 8

Difficulty: MEDIUM
Tags: String algorithms

Data structures
Skill types: Data structures
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)

Starter code:
#User function Template for python3

class Solution:

    def printMinNumberForPattern(ob,S):

        # code here 

Solutions:
class Solution:

	def printMinNumberForPattern(ob, S):
		start = 0
		prev = S[0]
		result = ''
		S = S + '#'
		for x in range(1, len(S)):
			if prev == S[x]:
				continue
			elif prev == 'I':
				tmp = x + 1 if S[x] == '#' else x
				start += 1 if start != 0 else 0
				while start < tmp:
					start += 1
					result += str(start)
				prev = S[x]
			else:
				tmp = x + 1
				while start < tmp:
					result += str(tmp)
					tmp -= 1
				start = x
				prev = S[x]
		return result


class Solution:

	def printMinNumberForPattern(ob, S):
		st = []
		ans = ''
		for i in range(len(S) + 1):
			st.append(i + 1)
			if i == len(S) or S[i] == 'I':
				while len(st) > 0:
					ans += str(st.pop())
		return ans


class Solution:

	def printMinNumberForPattern(ob, s):
		if not s or len(s) <= 0:
			return ''
		base_list = ['1']
		for i in range(1, len(s) + 1):
			base_list.append(str(i + 1))
		last_D = -1
		for i in range(1, len(base_list)):
			if s[i - 1] == 'D':
				if last_D < 0:
					last_D = i - 1
				v = base_list[i]
				del base_list[i]
				base_list.insert(last_D, str(v))
			else:
				last_D = -1
		return ''.join(base_list)


class Solution:

	def printMinNumberForPattern(ob, S):
		ans = ''
		count = 1
		start = 1
		for i in S:
			if i == 'D':
				count += 1
			else:
				ind = count
				while start <= ind:
					if str(ind) not in ans:
						ans += str(ind)
					ind -= 1
				start = count
				count += 1
		while start <= count:
			if str(count) not in ans:
				ans += str(count)
			count -= 1
		return ans


class Solution:

	def printMinNumberForPattern(ob, S):

		def isvalid(prev, canuse, s, path):
			canuse[prev - 1] = False
			if s == '':
				return True
			start = 1
			end = 10
			if s[0] == 'D':
				end = prev
			else:
				start = prev + 1
			for i in range(start, end):
				path += [i]
				if canuse[i - 1] and isvalid(i, canuse, s[1:], path):
					return True
				path.pop()
			canuse[prev - 1] = True
			return False
		canuse = [True] * 9
		for i in range(1, 10):
			path = [i]
			if isvalid(i, canuse, S, path):
				return ''.join([str(i) for i in path])
		return ''


class Solution:

	def printMinNumberForPattern(ob, S):
		l = c = 1
		s = ''
		for i in S:
			if i == 'I':
				s += ''.join([str(x) for x in range(c, l - 1, -1) if str(x) not in s])
				l = c
			c += 1
		s += ''.join([str(c) for c in range(c, l - 1, -1) if str(c) not in s])
		return s


class Solution:

	def solve(self, s, k, curr, c):
		if k == len(s):
			self.ans = 0
			for i in curr:
				self.ans = self.ans * 10 + i
			self.found = True
			return True
		if s[k] == 'I':
			for i in range(curr[-1] + 1, 10):
				if i in curr:
					continue
				curr.append(i)
				if self.solve(s, k + 1, curr, i):
					return True
				curr.pop()
		else:
			for i in range(curr[-1] - 1, 0, -1):
				if i in curr:
					continue
				curr.append(i)
				if self.solve(s, k + 1, curr, i):
					return True
				curr.pop()
		return False

	def printMinNumberForPattern(self, S):
		self.found = False
		curr = []
		for i in range(1, 10):
			curr.append(i)
			if self.solve(S, 0, curr, i):
				return self.ans
			curr.pop()
		return -1


class Solution:

	def printMinNumberForPattern(self, S):
		ans = []
		(i, N) = (0, len(S))
		while i < N and S[i] == 'D':
			i += 1
		if i > 0:
			ans.extend(reversed(range(1, i + 2)))
		while i < N:
			(ic, dc) = (0, 0)
			while i < N and S[i] == 'I':
				ic += 1
				i += 1
			while i < N and S[i] == 'D':
				dc += 1
				i += 1
			mn = len(ans) + 1
			if mn > 1:
				ic -= 1
			ans.extend(range(mn, mn + ic))
			ans.extend(reversed(range(mn + ic, mn + ic + dc + 1)))
		return ''.join((str(v) for v in ans))


class Solution:

	def printMinNumberForPattern(ob, s):
		ans = ''
		st = []
		num = 1
		for char in s:
			if char == 'D':
				st.append(num)
				num += 1
			else:
				st.append(num)
				num += 1
				while st:
					ans += str(st.pop())
		st.append(num)
		while st:
			ans += str(st.pop())
		return ans


class Solution:

	def printMinNumberForPattern(ob, S):
		(l, c, ans) = (1, 1, '')
		for i in S:
			if i == 'D':
				c += 1
			else:
				x = c
				while l <= x:
					if str(x) not in ans:
						ans += str(x)
					x -= 1
				l = c
				c += 1
		while c >= l:
			if str(c) not in ans:
				ans += str(c)
			c -= 1
		return ans


class Solution:

	def printMinNumberForPattern(ob, S):
		d = 0
		i = 0
		l = []
		n = len(S)
		for k in range(n):
			if S[k] == 'D':
				d += 1
				if S[k - 1] == 'I' and k > 0:
					l += [i]
					i = 0
			else:
				i += 1
				if S[k - 1] == 'D' and k > 0:
					l += [-d]
					d = 0
		if i:
			l += [i]
		if d:
			l += [-d]
		l += [0]
		mm = len(l)
		m = l
		if m[0] > 0:
			ans = '1'
			ini = 2
		else:
			ans = str(-m[0] + 1)
			ini = -m[0] + 2
		for i in range(mm):
			if m[i] < 0:
				ite = -m[i]
				st = ini - 2
				while ite:
					ans += str(st)
					ite -= 1
					st -= 1
			elif m[i] > 0:
				ite = m[i]
				st = ini
				while ite - 1:
					ans += str(st)
					ite -= 1
					st += 1
					ini += 1
				ans += str(st - m[i + 1])
				ini = st - m[i + 1] + 1
		return ans


class Solution:

	def printMinNumberForPattern(ob, s):
		st = []
		l = len(s)
		c = 1
		ans = ''
		for i in range(len(s)):
			if s[i] == 'I':
				st.insert(0, c)
				for j in range(len(st)):
					ans += str(st[j])
				c += 1
				st = []
			else:
				st.insert(0, c)
				c += 1
			if i == len(s) - 1:
				st.insert(0, c)
				for j in range(len(st)):
					ans += str(st[j])
				st = []
		return ans


class Solution:

	def printMinNumberForPattern(ob, S):
		st = ''
		i = 0
		num = 1
		if S[0] == 'I':
			st += str(num)
			num += 1
		while i < len(S):
			if S[i] == 'I':
				j = i
				count = 0
				while j < len(S):
					if S[j] == 'I':
						j += 1
						count += 1
					else:
						break
				for p in range(count - 1):
					st += str(num)
					num += 1
				i = j
			elif S[i] == 'D':
				j = i
				count = 0
				while j < len(S):
					if S[j] == 'D':
						j += 1
						count += 1
					else:
						break
				before = num
				num = num + count
				after = num
				while num >= before:
					st += str(num)
					num -= 1
				num = after + 1
			i = j
		if S[-1] == 'I':
			st += str(num)
		return st


from collections import deque

class Solution:

	def printMinNumberForPattern(ob, S):
		stack = deque()
		num = 1
		s = 0
		for c in S:
			stack.append(num)
			num += 1
			if c == 'I':
				while stack:
					s = s * 10 + stack.pop()
		stack.append(num)
		num += 1
		while stack:
			s = s * 10 + stack.pop()
		return s


class Solution:

	def printMinNumberForPattern(ob, S):
		pattern = S
		res = ''
		last_used = 0
		stack = list()
		for i in range(len(pattern)):
			last_used += 1
			stack.append(last_used)
			if pattern[i] == 'I':
				while stack:
					res += '{}'.format(stack.pop(len(stack) - 1))
		stack.append(last_used + 1)
		while stack:
			res += '{}'.format(stack.pop(len(stack) - 1))
		return res


class Solution:

	def printMinNumberForPattern(ob, S):
		new_s = ''
		stack = []
		for i in range(len(S) + 1):
			stack.append(i + 1)
			if i == len(S) or S[i] == 'I':
				while stack:
					new_s += str(stack.pop())
		return new_s


class Solution:

	def printMinNumberForPattern(ob, S):
		n = len(S)
		l = []
		c = 1
		d = 0
		i = 0
		while i < n:
			if S[i] == 'I' and i == 0:
				l.append(c)
				c += 1
			if S[i] == 'D':
				d += 1
			j = i + 1
			while j < n and S[j] == 'D':
				d += 1
				j += 1
			k = d
			while d >= 0:
				l.append(c + d)
				d -= 1
			d = 0
			c += k + 1
			i = j
		return ''.join(map(str, l))


class Solution:

	def printMinNumberForPattern(ob, Str):
		ans = ''
		i = 0
		cur = 1
		dCount = 0
		while i < len(Str):
			ch = Str[i]
			if i == 0 and ch == 'I':
				ans += str(cur)
				cur += 1
			if ch == 'D':
				dCount += 1
			j = i + 1
			while j < len(Str) and Str[j] == 'D':
				dCount += 1
				j += 1
			k = dCount
			while dCount >= 0:
				ans += str(cur + dCount)
				dCount -= 1
			cur += k + 1
			dCount = 0
			i = j
		return ans


class Solution:

	def printMinNumberForPattern(ob, S):
		ans = []
		st = []
		num = 1
		for i in range(0, len(S)):
			if S[i] == 'I':
				st.append(num)
				num = num + 1
				while len(st) != 0:
					ans.append(str(st[len(st) - 1]))
					st.pop()
			else:
				st.append(num)
				num = num + 1
		st.append(num)
		while len(st) != 0:
			ans.append(str(st[len(st) - 1]))
			st.pop()
		return ''.join(ans)


class Solution:

	def printMinNumberForPattern(ob, S):
		min_avail = 3
		position_I = 0
		v = []
		if S[0] == 'I':
			position_I = 1
			v.append(1)
			v.append(2)
		else:
			v.append(2)
			v.append(1)
		n = len(S)
		for i in range(1, n):
			if S[i] == 'I':
				v.append(min_avail)
				min_avail += 1
				position_I = i + 1
			else:
				v.append(v[i])
				for j in range(position_I, i + 1):
					v[j] += 1
				min_avail += 1
		for i in range(len(v)):
			v[i] = str(v[i])
		return ''.join(v)


class Solution:

	def printMinNumberForPattern(ob, S):
		from queue import LifoQueue
		st = LifoQueue(maxsize=9)
		ans = ''
		num = 1
		for i in S:
			if i == 'D':
				st.put(num)
				num += 1
			else:
				st.put(num)
				num += 1
				while st.qsize() > 0:
					ans = ans + str(st.get())
		st.put(num)
		while st.qsize() > 0:
			ans = ans + str(st.get())
		return ans


class Solution:

	def printMinNumberForPattern(ob, S):
		seti = set([1])
		lis = [1]
		n = len(S)
		val = 1
		i = 0
		while i < n and val < 10:
			if S[i] == 'I':
				while val in seti:
					val += 1
				lis.append(val)
				seti.add(val)
				i += 1
				val += 1
			else:
				counti = 0
				j = i
				while j < n and S[j] == 'D':
					counti += 1
					j += 1
				t = lis[-1] + counti
				seti.discard(lis[-1])
				val = 1
				lis[-1] = t
				seti.add(t)
				t -= 1
				while i < j:
					lis.append(t)
					seti.add(t)
					t -= 1
					i += 1
		op = ''
		for i in lis:
			op += str(i)
		return op


class Solution:

	def printMinNumberForPattern(ob, S):
		last = 'None'
		S = S + 'I'
		number = '0'
		sequentuals = 1
		for (count, value) in enumerate(S[:-1]):
			if value == 'I':
				sequentuals = 1
				if S[count + 1] == 'I' and last == 'None':
					number += '1'
				if S[count + 1] == 'I':
					number += str(int(max(number)) + 1)
				if not S[count + 1] == 'I' and last == 'None':
					number += '1'
				else:
					pass
				last = 'I'
			else:
				if not last == 'D':
					while S[count + sequentuals] == 'D':
						sequentuals += 1
					number += str(int(max(number)) + sequentuals + 1)
				number += str(int(number[-1]) - 1)
				last = 'D'
		return number[1:]


class Solution:

	def printMinNumberForPattern(ob, S):
		d_count = 0
		biggest_num_added = 0
		res = ''
		for x in range(len(S)):
			if S[x] == 'I':
				for i in range(biggest_num_added + d_count + 1, biggest_num_added, -1):
					res += str(i)
					biggest_num_added += 1
				d_count = 0
			else:
				d_count += 1
			if S[x] == 'I' and x == len(S) - 1:
				res += str(biggest_num_added + 1)
		if d_count > 0:
			for i in range(biggest_num_added + d_count + 1, biggest_num_added, -1):
				res += str(i)
			d_count = 0
		return res


class Solution:

	def printMinNumberForPattern(ob, pattern):
		count = 0
		for i in pattern:
			if i == 'D':
				count = count + 1
		nums = [1, 2, 3, 4, 5, 6, 7, 8, 9]
		nums = nums[:len(pattern) + 1]
		for i in range(count):
			for j in range(len(pattern)):
				if pattern[j] == 'I':
					if nums[j] < nums[j + 1]:
						continue
					else:
						(nums[j], nums[j + 1]) = (nums[j + 1], nums[j])
				elif pattern[j] == 'D':
					if nums[j] > nums[j + 1]:
						continue
					else:
						(nums[j], nums[j + 1]) = (nums[j + 1], nums[j])
		final_ans = ''
		for ele in nums:
			ele = str(ele)
			final_ans += ele
		return final_ans


class Solution:

	def printMinNumberForPattern(ob, S):
		stack = []
		ans = []
		cnt = 1
		for i in range(len(S)):
			if S[i] == 'D':
				stack.append(str(cnt))
				cnt += 1
			elif S[i] == 'I':
				stack.append(str(cnt))
				cnt += 1
				while stack:
					ans.append(stack.pop())
		stack.append(str(cnt))
		while stack:
			ans.append(stack.pop())
		return ''.join(ans)


class Solution:

	def printMinNumberForPattern(ob, S):
		t = []
		stack = []
		num = 1
		for i in range(len(S)):
			if S[i] == 'D':
				stack += [num]
				num += 1
			else:
				stack += [num]
				num += 1
				while len(stack) > 0:
					t += [str(stack.pop())]
		stack += [num]
		while len(stack) > 0:
			t += [str(stack.pop())]
		return ''.join(t)


class Solution:

	def printMinNumberForPattern(ob, S):
		(l, c, ans) = (1, 1, '')
		for i in S:
			if i == 'D':
				c += 1
			else:
				x = c
				while l <= x:
					if str(x) not in ans:
						ans += str(x)
					x -= 1
				l = c
				c += 1
		while c >= l:
			if str(c) not in ans:
				ans += str(c)
			c -= 1
		return ans
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		S = str(input())
		ob = Solution()
		print(ob.printMinNumberForPattern(S))


class Solution:

	def printMinNumberForPattern(self, S):
		n = len(S)
		arr = [i + 1 for i in range(n + 1)]

		def reverse(i, j):
			while i < j:
				(arr[i], arr[j]) = (arr[j], arr[i])
				i += 1
				j -= 1
		i = 0
		while i < n:
			if S[i] == 'D':
				start = i
				while i < n and S[i] == 'D':
					i += 1
				reverse(start, i)
			else:
				i += 1
		ans = 0
		for i in range(n + 1):
			ans = ans * 10 + arr[i]
		return ans
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		S = str(input())
		ob = Solution()
		print(ob.printMinNumberForPattern(S))


class Solution:

	def printMinNumberForPattern(ob, S):
		number = ''
		prev_i = 1
		for (index, i) in enumerate(S):
			if i == 'I':
				for d in range(prev_i, index + 2)[::-1]:
					number += str(d)
				prev_i = index + 2
		number += ''.join([str(x) for x in range(len(S) + 1, prev_i - 1, -1)])
		return int(number)
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		S = str(input())
		ob = Solution()
		print(ob.printMinNumberForPattern(S))


class Solution:

	def printMinNumberForPattern(ob, s):
		a = 1
		poi = 0
		l = []
		if s[0] == 'I':
			l.append(1)
			l.append(2)
			poi = 1
			a = 3
		else:
			l.append(2)
			l.append(1)
			poi = 0
			a = 3
		for i in range(1, len(s)):
			if s[i] == 'I':
				l.append(a)
				a += 1
				poi = i + 1
			else:
				l.append(l[i])
				for j in range(poi, i + 1):
					l[j] += 1
				a += 1
		ans = ''
		for i in l:
			ans += str(i)
		return ans
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		S = str(input())
		ob = Solution()
		print(ob.printMinNumberForPattern(S))


class Solution:

	def printMinNumberForPattern(ob, S):
		(ind, stack, ans) = (1, [], '')
		for i in S:
			if i == 'D':
				stack.append(ind)
				ind += 1
			else:
				stack.append(ind)
				ind += 1
				while stack:
					ans += str(stack.pop())
		stack.append(ind)
		while stack:
			ans += str(stack.pop())
		return ans
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		S = str(input())
		ob = Solution()
		print(ob.printMinNumberForPattern(S))


class Solution:

	def printMinNumberForPattern(ob, S):
		curr_max = 0
		last_entry = 0
		i = 0
		ans = ''
		while i < len(S):
			noOfNextD = 0
			if S[i] == 'I':
				j = i + 1
				while j < len(S) and S[j] == 'D':
					noOfNextD += 1
					j += 1
				if i == 0:
					curr_max = noOfNextD + 2
					last_entry += 1
					ans += str(last_entry)
					ans += str(curr_max)
					last_entry = curr_max
				else:
					curr_max += noOfNextD + 1
					last_entry = curr_max
					ans += str(last_entry)
				for k in range(noOfNextD):
					last_entry -= 1
					ans += str(last_entry)
					i += 1
			elif S[i] == 'D':
				if i == 0:
					j = i + 1
					while j < len(S) and S[j] == 'D':
						noOfNextD += 1
						j += 1
					curr_max = noOfNextD + 2
					ans += str(curr_max)
					ans += str(curr_max - 1)
					last_entry = curr_max - 1
				else:
					ans += str(last_entry - 1)
					last_entry -= 1
			i += 1
		return ans


class Solution:

	def printMinNumberForPattern(ob, S):
		ans = 1
		dig = 1
		i = 0
		while i < len(S):
			if S[i] == 'I':
				ans = ans * 10 + dig + 1
				dig = dig + 1
				i += 1
			else:
				cnt = 1
				while i < len(S) and S[i] == 'D':
					x = ans % pow(10, cnt)
					ans = ans // pow(10, cnt)
					ans = ans * 10 + dig + 1
					dig = dig + 1
					ans = ans * pow(10, cnt) + x
					cnt += 1
					i += 1
		return ans


class Solution:

	def printMinNumberForPattern(ob, S):
		v = []
		position = 0
		if S[0] == 'I':
			v.append(1)
			v.append(2)
			position += 1
		else:
			v.append(2)
			v.append(1)
		lastnum = 2
		for i in range(1, len(S)):
			if S[i] == 'I':
				v.append(lastnum + 1)
				lastnum += 1
				position = i + 1
			else:
				for j in range(position, i + 1):
					v[j] += 1
				v.append(v[-1] - 1)
				lastnum += 1
		ans = ''
		for i in v:
			ans += str(i)
		return ans


class Solution:

	def printMinNumberForPattern(ob, S):
		st = []
		num = 1
		ans = ''
		for i in range(len(S)):
			ch = S[i]
			if ch == 'D':
				st.append(num)
				num += 1
			elif ch == 'I':
				st.append(num)
				num += 1
				while len(st) != 0:
					ans += str(st[-1])
					st.pop()
		st.append(num)
		while len(st) != 0:
			ans += str(st[-1])
			st.pop()
		return ans


class Solution:

	def printMinNumberForPattern(ob, s):
		ans = ''
		p = 1
		temp = 1
		cond = False
		for i in s:
			if i == 'I':
				if not cond:
					ans += str(p)
				else:
					k = p
					while k >= temp:
						ans += str(k)
						k -= 1
					cond = False
			elif not cond:
				temp = p
				cond = True
			p += 1
		if cond:
			k = p
			while k >= temp:
				ans += str(k)
				k -= 1
		else:
			ans += str(p)
		return ans


from collections import deque

class Solution:

	def printMinNumberForPattern(ob, S):
		position = 0
		v = []
		lastnum = 0
		if S[0] == 'I':
			v.append(1)
			v.append(2)
			position = 1
			lastnum = 2
		else:
			v.append(2)
			v.append(1)
			pos = 1
			lastnum = 2
		for i in range(1, len(S)):
			if S[i] == 'I':
				v.append(lastnum + 1)
				lastnum += 1
				position = i + 1
			else:
				for j in range(position, i + 1):
					v[j] += 1
				v.append(v[-1] - 1)
				lastnum += 1
		answer = ''
		for j in v:
			answer += str(j)
		return answer


class Solution:

	def printMinNumberForPattern(ob, S):
		if len(S) >= 9:
			return -1

		def count_D(S):
			cnt = int()
			for ch in S:
				if ch == 'I':
					break
				cnt += 1
			return cnt
		nums = [0] * 10

		def smallest_left():
			for i in range(1, 10):
				if nums[i] == 0:
					return i
		if S[0] == 'D':
			answer = count_D(S) + 1
		else:
			answer = 1
		last_max = answer
		nums[answer] = 1
		for i in range(len(S)):
			if S[i] == 'D':
				l = last_max
				while nums[l] != 0:
					l -= 1
				answer = answer * 10 + l
				nums[l] = 1
			else:
				D_cnt = count_D(S[i + 1:])
				answer = answer * 10 + D_cnt + last_max + 1
				last_max += D_cnt + 1
			nums[answer % 10] = 1
		return answer


class Solution:

	def printMinNumberForPattern(ob, s):
		string = ''
		stack = []
		count = 1
		for i in range(len(s)):
			if s[i] == 'I':
				string += str(count)
				while stack:
					string += str(stack.pop())
				count += 1
			else:
				stack.append(count)
				count += 1
		stack.append(count)
		while stack:
			string += str(stack.pop())
		return string


class Solution:

	def printMinNumberForPattern(ob, S):
		st = []
		j = 1
		ans = []
		for c in S:
			if c == 'D':
				st.append(j)
				j += 1
			else:
				st.append(j)
				j += 1
				while st:
					ans.append(st.pop())
		st.append(j)
		while st:
			ans.append(st.pop())
		return ''.join(map(str, ans))


class Solution:

	def printMinNumberForPattern(ob, S):
		res = ''
		j = 1
		li = []
		for s in S:
			if s == 'D':
				li.append(j)
				j += 1
			else:
				li.append(j)
				j += 1
				while len(li) > 0:
					res += str(li.pop())
		li.append(j)
		while len(li) > 0:
			res += str(li.pop())
		return res


class Solution:

	def printMinNumberForPattern(ob, S):
		res = []
		i = 0
		curr = 1
		m = 0
		while i < len(S):
			if S[i] == 'I':
				c = 0
				while i < len(S) and S[i] == 'I':
					c += 1
					i += 1
				m = max(m, curr)
				for x in range(c):
					res.append(curr)
					curr = m + 1
					m = max(m, curr)
			else:
				c = 0
				while i < len(S) and S[i] == 'D':
					c += 1
					i += 1
				t = temp = curr + c
				for x in range(c):
					res.append(t)
					m = max(m, t)
					t -= 1
				curr = t
		res.append(curr)
		ans = ''
		for i in res:
			ans += str(i)
		return ans


class Solution:

	def printMinNumberForPattern(self, S):
		res = 1
		temp = 1
		num = 1
		running = 1
		for I in S:
			if I == 'I':
				res = res * 10 + num + 1
				running = num + 1
				temp = 1
			if I == 'D':
				res += temp
				res = res * 10 + running
				temp = temp * 10 + 1
			num += 1
		return res


class Solution:

	def printMinNumberForPattern(ob, S):
		arr = [str(i) for i in range(1, len(S) + 2)]
		ans = ''
		i = 0
		while i < len(S):
			if S[i] == 'I':
				ans = ans + arr.pop(0)
			else:
				count = 1
				while i < len(S) and S[i] != 'I':
					i += 1
					count += 1
				ans = ans + ''.join(arr[:count][::-1])
				del arr[:count]
			i += 1
		if len(arr) > 0 and S[-1] == 'I':
			ans = ans + ''.join(arr[:])
		return ans


class Solution:

	def printMinNumberForPattern(ob, S):
		n = len(S)
		nums = [str(n) for n in range(1, len(S) + 2)]
		result = []
		for idx in range(n):
			if S[idx] == 'I':
				result.append(nums.pop(0))
			else:
				count = 0
				down = idx
				while down < n and S[down] == 'D':
					count += 1
					down += 1
				result.append(nums.pop(0 + count))
		result.append(nums.pop(0))
		return int(''.join(result))


class Solution:

	def printMinNumberForPattern(ob, S):
		count = 0
		flag = 0
		i = 0
		ans = ''
		if len(S) == 1:
			if S[0] == 'D':
				return '21'
			else:
				return '12'
		while i < len(S):
			if S[i] == 'I':
				if flag == 0:
					ans += str(count + 1)
					count += 1
				else:
					flag = 0
			elif S[i] == 'D':
				flag = 1
				count += 1
				curr_count = count
				j = i + 1
				curr = 2
				while j < len(S) and S[j] == 'D':
					count += 1
					curr += 1
					curr_count += 1
					i += 1
					j += 1
				while curr:
					ans += str(count + 1)
					j -= 1
					curr -= 1
					count -= 1
				count = curr_count + 1
			i += 1
		return ans if S[-1] == 'D' else ans + str(count + 1)


class Solution:

	def printMinNumberForPattern(ob, pattern):
		result = []
		n = len(pattern)
		available = [str(x + 1) for x in range(9)]
		countD = [0 for x in range(len(pattern))]
		for i in range(n - 1, -1, -1):
			if pattern[i] == 'D':
				if i == n - 1:
					countD[i] = 1
				else:
					countD[i] = 1 + countD[i + 1]
		for i in range(n):
			result.append(available[0 + countD[i]])
			del available[0 + countD[i]]
		result.append(available[0])
		return int(''.join(result))


class Solution:

	def printMinNumberForPattern(ob, pattern):
		result = []
		available = [str(x + 1) for x in range(9)]
		for i in range(len(pattern)):
			countD = 0
			j = i
			while j < len(pattern) and pattern[j] == 'D':
				countD += 1
				j += 1
			result.append(available[0 + countD])
			del available[0 + countD]
		result.append(available[0])
		return int(''.join(result))


class Solution:

	def printMinNumberForPattern(ob, pattern):
		result = []
		n = len(pattern)
		available = [str(x + 1) for x in range(9)]
		for i in range(n):
			countD = 0
			j = i
			while j < n:
				if pattern[j] == 'I':
					break
				countD += 1
				j += 1
			result.append(available[0 + countD])
			del available[0 + countD]
		result.append(available[0])
		return int(''.join(result))


class Solution:

	def printMinNumberForPattern(ob, S):
		stack = []
		num = 1
		min_num = []
		for char in S:
			if char == 'D':
				stack.append(num)
				num += 1
			else:
				stack.append(num)
				num += 1
				while stack:
					min_num.append(str(stack.pop()))
		stack.append(num)
		while stack:
			min_num.append(str(stack.pop()))
		return ''.join(min_num)


class Solution:

	def printMinNumberForPattern(ob, S):
		b = 1
		d = b
		s = ''
		for c in S:
			if c == 'D':
				d += 1
			else:
				bb = d + 1
				while d >= b:
					s += str(d)
					d -= 1
				d = b = bb
		while d >= b:
			s += str(d)
			d -= 1
		return s


class Solution:

	def printMinNumberForPattern(ob, s):
		ans = ''
		i = 0
		dcnt = 0
		cur = 1
		while i < len(s):
			if i == 0 and s[i] == 'I':
				ans += str(cur)
				cur += 1
			if s[i] == 'D':
				dcnt += 1
			j = i + 1
			while j < len(s) and s[j] == 'D':
				dcnt += 1
				j += 1
			k = dcnt
			while dcnt >= 0:
				ans += str(cur + dcnt)
				dcnt -= 1
			cur += k + 1
			i = j
			dcnt = 0
		return ans


class Solution:

	def printMinNumberForPattern(ob, S):
		ans = ''
		stack = []
		num = 1
		for i in range(len(S)):
			if S[i] == 'D':
				stack.append(num)
				num += 1
			else:
				stack.append(num)
				num += 1
				while stack:
					ans += str(stack.pop())
		stack.append(num)
		while stack:
			ans += str(stack.pop())
		return ans


class Solution:

	def printMinNumberForPattern(ob, S):
		n = 1
		s = ''
		st = []
		for i in S:
			if i == 'D':
				st.append(n)
				n += 1
			else:
				st.append(n)
				n += 1
				while len(st) > 0:
					s += str(st.pop())
		st.append(n)
		while len(st) > 0:
			s += str(st.pop())
		return s


class Solution:

	def printMinNumberForPattern(ob, S):
		ans = ''
		stack = []
		i = 1
		s = S
		for j in s:
			if j == 'D':
				stack.append(i)
				i += 1
			else:
				stack.append(i)
				i += 1
				while stack != []:
					ele = stack[-1]
					stack.pop()
					ans += str(ele)
		stack.append(i)
		while stack != []:
			ele = stack[-1]
			ans += str(ele)
			stack.pop()
		return ans


class Solution:

	def printMinNumberForPattern(ob, S):
		stack = []
		num = 1
		res = ''
		for i in range(len(S)):
			stack.append(num)
			num += 1
			if S[i] == 'I':
				while len(stack) > 0:
					res += str(stack.pop())
		stack.append(num)
		while len(stack) > 0:
			res += str(stack.pop())
		return ''.join(res)


class Solution:

	def printMinNumberForPattern(ob, S):
		stack = []
		result = []
		for i in range(len(S) + 1):
			stack.append(i + 1)
			if i == len(S) or S[i] == 'I':
				while stack:
					result.append(str(stack.pop()))
		return int(''.join(result))


import heapq

class Solution:

	def printMinNumberForPattern(ob, S):
		heap = []
		for i in range(10, 1, -1):
			heap.append(str(i))
		op = '1'
		last_increasing_value_index = 0
		for i in range(len(S)):
			if S[i] == 'I':
				op = op + heap.pop()
				last_increasing_value_index = i + 1
			else:
				op = op[:last_increasing_value_index] + heap.pop() + op[last_increasing_value_index:]
		return op


import heapq

class Solution:

	def printMinNumberForPattern(ob, S):
		heap = []
		for i in range(2, 10):
			heapq.heappush(heap, str(i))
		op = '1'
		last_increasing_value_index = 0
		for i in range(len(S)):
			if S[i] == 'I':
				op = op + heapq.heappop(heap)
				last_increasing_value_index = i + 1
			else:
				op = op[:last_increasing_value_index] + heapq.heappop(heap) + op[last_increasing_value_index:]
		return op


class Solution:

	def printMinNumberForPattern(ob, seq):
		n = len(seq)
		if n >= 9:
			return '-1'
		result = [None] * (n + 1)
		count = 1
		for i in range(n + 1):
			if i == n or seq[i] == 'I':
				for j in range(i - 1, -2, -1):
					result[j + 1] = int('0' + str(count))
					count += 1
					if j >= 0 and seq[j] == 'I':
						break
		return ''.join((str(item) for item in result))


class Solution:

	def printMinNumberForPattern(ob, S):
		temp = 1
		ans = 1
		num = 1
		i = 1
		for ch in S:
			if ch == 'I':
				ans = ans * 10 + num + 1
				i = num + 1
				temp = 1
			else:
				ans += temp
				ans = ans * 10 + i
				temp = temp * 10 + 1
			num += 1
		return ans


class Solution:

	def printMinNumberForPattern(ob, S):
		n = len(S)
		_S = ''
		stack = []
		num = 1
		for i in range(n):
			if S[i] == 'D':
				stack.append(num)
				num += 1
			elif S[i] == 'I':
				stack.append(num)
				num += 1
				while stack:
					_S += str(stack[-1])
					stack.pop()
		stack.append(num)
		while stack:
			_S += str(stack[-1])
			stack.pop()
		return _S


class Solution:

	def printMinNumberForPattern(ob, s):
		st = []
		res = ''
		l = len(s)
		for i in range(l + 1):
			st.append(i + 1)
			if i == l or s[i] == 'I':
				while len(st) > 0:
					res += str(st.pop())
		return res


from itertools import permutations

class Solution:

	def printMinNumberForPattern(ob, S):
		stack = []
		count = 1
		ans = ''
		for char in S:
			if char == 'D':
				stack.append(count)
				count = count + 1
			if char == 'I':
				stack.append(count)
				count = count + 1
				while len(stack) != 0:
					temp = stack.pop(-1)
					ans = ans + str(temp)
		stack.append(count)
		while len(stack) != 0:
			temp = stack.pop(-1)
			ans = ans + str(temp)
		return ans


from itertools import permutations

class Solution:

	def printMinNumberForPattern(ob, S):
		num = []
		count = 1
		for i in range(len(S) + 1):
			num.append(count)
			count = count + 1
		permList = permutations(num)
		for ele in list(permList):
			flag = False
			for i in range(1, len(ele)):
				if S[i - 1] == 'I' and ele[i - 1] < ele[i]:
					flag = True
					continue
				elif S[i - 1] == 'D' and ele[i - 1] > ele[i]:
					flag = True
					continue
				else:
					flag = False
					break
			if flag == True:
				st = ''
				for item in ele:
					st = st + str(item)
				return st


import sys

def mgc(vis, cur, S, i):
	if i >= len(S):
		return int(cur)
	ans = sys.maxsize
	for j in range(1, 10):
		if j not in vis:
			if S[i] == 'I':
				if j > int(cur[-1]):
					vis.add(j)
					ans = min(ans, mgc(vis, cur + str(j), S, i + 1))
					vis.remove(j)
			elif j < int(cur[-1]):
				vis.add(j)
				ans = min(ans, mgc(vis, cur + str(j), S, i + 1))
				vis.remove(j)
	return ans

class Solution:

	def printMinNumberForPattern(ob, S):
		ans = sys.maxsize
		for i in range(1, 9):
			ans = min(ans, mgc({i}, str(i), S, 0))
		return ans


class Solution:

	def printMinNumberForPattern(ob, S):
		stack = []
		temp = []
		k = 1
		for i in S:
			stack = [k] + stack
			if i == 'I':
				temp += stack
				stack = []
			k += 1
		stack = [k] + stack
		temp += stack
		num = 0
		p = 1
		for i in range(len(temp) - 1, -1, -1):
			num += p * temp[i]
			p *= 10
		return num