You are given a string str of length n. You want to choose a non-zero integer k (k<=n), such that you can perform the following operation:
Take the prefix of the string of length k and append the reverse of it to itself.
Your task is to find the lexicographically smallest string you can get.
Example 1:
Input:
str = "bvdfndkn"
Output:
bb
Explanation:
If we choose k=1, prefix of length k will be "b", reverse of
this prefix will be "b" itself, when we append both we get "bb",
"bb" is the lexicographically smallest string you can get.
If you choose k>1, the resulting string will not be 
lexicographically smaller than "bb".
Example 2:
Input:
str = "casd"
Output:
caac
Explanation:
If we choose k=2, prefix of length k will be "ca", reverse of
this prefix will be "ac", when we append both we get "caac",
"caac" is the lexicographically smallest string you can get.
Your Task:
You don't need to read input or print anything. Your task is to complete the function stringMirror() which takes a String str as input, and returns the lexicographically smallest string.
Expected Time Complexity: O(|str|)
Expected Space Complexity: O(|str|)
Constraints:
1 <= |str| <= 10^{5}

Source: geeksforgeeks | Difficulty: EASY
Tags: String algorithms

Data structures

Mathematics

Starter code: class Solution:

    def stringMirror(self, str : str) -> str:

        # code here

        



Solutions:
class Solution:

	def stringMirror(self, str: str) -> str:
		var = str[0]
		for i in range(1, len(str)):
			if str[0] == str[1]:
				break
			if str[i] <= str[i - 1]:
				var += str[i]
			else:
				break
		var += var[::-1]
		return var


class Solution:

	def stringMirror(self, str: str) -> str:
		i = 0
		s = str[0]
		for i in range(1, len(str)):
			if str[i] < str[i - 1] or (i > 1 and str[i] == str[i - 1]):
				s += str[i]
			else:
				break
		rev = s[::-1]
		return s + rev


class Solution:

	def stringMirror(self, str: str) -> str:
		s = ''
		s += str[0]
		for i in range(1, len(str)):
			if i != 1 and s[i - 1] == str[i]:
				s += str[i]
			elif s[i - 1] > str[i]:
				s += str[i]
			else:
				break
		st = s
		s = s[::-1]
		st += s
		return st


class Solution:

	def stringMirror(self, str: str) -> str:
		arr = []
		arr.append(str[0])
		count = 0
		if len(str) > 1:
			for i in range(1, len(str)):
				if str[0] == str[1]:
					break
				if ord(str[i]) <= ord(arr[count]):
					arr.append(str[i])
					count += 1
				else:
					break
		for i in range(count, -1, -1):
			arr.append(arr[i])
		str1 = ''.join(arr)
		return str1


class Solution:

	def stringMirror(self, str: str) -> str:
		count = 1
		l = len(str)
		if l == 1:
			return 2 * str[0]
		elif str[0] == str[1]:
			return 2 * str[0]
		for i in range(1, l):
			if str[i - 1] < str[i]:
				break
			else:
				count += 1
		return str[:count] + str[:count][::-1]


class Solution:

	def stringMirror(self, str: str) -> str:
		stk = []
		n = len(str)
		if n == 1:
			return 2 * str[0]
		if str[0] == str[1]:
			return 2 * str[0]
		stk.append(str[0])
		for i in range(1, n):
			if stk[-1] >= str[i]:
				stk.append(str[i])
			else:
				break
		ans = ''.join(stk)
		return ans + ans[::-1]


class Solution:

	def stringMirror(self, str: str) -> str:
		rs = 1
		strLen = len(str)
		if strLen > 1 and str[0] == str[1]:
			return str[0:2]
		while rs < strLen and str[rs] <= str[rs - 1]:
			rs += 1
		return str[0:rs] + str[::-1][-rs:]


class Solution:

	def stringMirror(self, str: str) -> str:
		n = len(str)
		temp = str[0]
		for left in range(1, n):
			if left != 1 and temp[left - 1] == str[left]:
				temp += str[left]
			elif temp[left - 1] > str[left]:
				temp += str[left]
			else:
				break
		reverse_temp = temp[::-1]
		temp += reverse_temp
		return temp


class Solution:

	def stringMirror(self, str1: str) -> str:
		x = ''
		p = 'zzzzzzzzzzz'
		for i in str1:
			x = x + i
			r = x + x[::-1]
			if r < p:
				p = r
			else:
				return p
		return p


class Solution:

	def stringMirror(self, str: str) -> str:
		new_string = ''
		ans = ''
		new_string = str[0]
		for i in range(1, len(str)):
			if str[i - 1] >= str[i] and str[0] != str[1]:
				new_string = new_string + str[i]
			else:
				break
		ans = new_string
		for i in range(len(new_string) - 1, -1, -1):
			new_string += ans[i]
		return new_string


class Solution:

	def stringMirror(self, str: str) -> str:
		m = 0
		for t in range(len(str) - 1):
			if t == 0:
				if str[t + 1] >= str[t]:
					m = t + 1
					break
			elif str[t + 1] > str[t]:
				m = t + 1
				break
			m = t + 2
		if len(str) == 1:
			pref = str
		else:
			pref = str[:m]
		suff = pref[::-1]
		return pref + suff


class Solution:

	def stringMirror(self, str):
		lst = str[0]
		tmp = str[0]
		for i in range(1, len(str)):
			if str[i] < lst:
				lst = str[i]
				tmp += lst
			else:
				break
		ans1 = tmp
		ans1 += tmp[::-1]
		tmp = str[0]
		lst = tmp
		for i in range(1, len(str)):
			if str[i] <= lst:
				lst = str[i]
				tmp += lst
			else:
				break
		ans2 = tmp + tmp[::-1]
		return min(ans1, ans2)


class Solution:

	def stringMirror(self, str: str) -> str:
		if len(str) > 1:
			if str[0] == str[1]:
				return str[0] * 2
		p = len(str)
		for i in range(len(str) - 1):
			if ord(str[i + 1]) > ord(str[i]):
				p = i + 1
				break
		return str[:p] + str[:p][::-1]


class Solution:

	def stringMirror(self, str: str) -> str:
		last = str[0]
		plen = 1
		for i in range(1, len(str)):
			if last >= str[i] and str[0] != str[1]:
				last = str[i]
				plen += 1
			else:
				break
		ans = str[:plen]
		for j in range(plen):
			ans += ans[plen - j - 1]
		return ans


class Solution:

	def stringMirror(self, s: str) -> str:
		i = 1
		while i < len(s) and s[i] < s[i - 1]:
			i += 1
		s1 = s[0:i]
		s1 += s1[::-1]
		i = 1
		while i < len(s) and s[i] <= s[i - 1]:
			i += 1
		s2 = s[0:i]
		s2 += s2[::-1]
		return s1 if s1 < s2 else s2


class Solution:

	def stringMirror(self, str: str) -> str:
		a = str[0]
		str1 = ''
		str1 += a
		if len(str) > 1 and a == str[1]:
			return a + a[::-1]
		for i in range(1, len(str)):
			if a >= str[i]:
				str1 += str[i]
				a = str[i]
			else:
				break
		d = str1 + str1[::-1]
		return d


import copy

class Solution:

	def stringMirror(self, s: str) -> str:
		res = [s[0]]
		prev = [s[0]]
		for i in range(1, len(s)):
			res.append(s[i])
			temp = res[::-1]
			v1 = res + temp
			temp2 = prev[::-1]
			v2 = prev + temp2
			if v1 <= v2:
				prev = res.copy()
			else:
				return ''.join(prev + prev[::-1])
		return ''.join(res + res[::-1])


class Solution:

	def stringMirror(self, str: str) -> str:
		length = len(str)
		smallest_string = str[0] * 2
		for i in range(1, length):
			temp = str[0:i + 1] + str[i::-1]
			if temp <= smallest_string:
				smallest_string = temp
			else:
				return smallest_string
		return smallest_string


class Solution:

	def stringMirror(self, str: str) -> str:
		length = len(str)
		smallest_string = str[0]
		for i in range(1, length):
			if str[i] < str[i - 1] or (i > 1 and str[i] == str[i - 1]):
				smallest_string += str[i]
			else:
				break
		return smallest_string + smallest_string[::-1]


class Solution:

	def stringMirror(self, str: str) -> str:
		st = str[0] * 2
		for i in range(1, len(str)):
			if str[:i + 1] + str[i::-1] <= st:
				st = str[:i + 1] + str[i::-1]
			else:
				return st
		return st


class Solution:

	def stringMirror(self, str: str) -> str:
		l = len(str)
		if l == 1:
			return 2 * str
		if l == 2:
			return min(2 * str[0], str + str[::-1])
		for i in range(1, l):
			if str[0:i] + str[i - 1::-1] < str[0:i + 1] + str[i::-1]:
				return str[0:i] + str[i - 1::-1]
		return str[0:i + 1] + str[i::-1]


class Solution:

	def stringMirror(self, str: str) -> str:
		ch = str[0]
		ans = str[0]
		if len(str) > 1:
			if ans == str[1]:
				return ans + ans
		for c in str[1:]:
			if c <= ch:
				ans += c
				ch = c
			else:
				break
		return ans + ans[::-1]


class Solution:

	def stringMirror(self, s: str) -> str:
		if len(s) == 1:
			return s * 2
		for (e, i) in enumerate(s[1:]):
			if s[:e + 1] + s[:e + 1][::-1] <= s[:e + 2] + s[:e + 2][::-1]:
				return s[:e + 1] + s[:e + 1][::-1]
		return s + s[::-1]


class Solution:

	def stringMirror(self, str: str) -> str:
		n = len(str)
		l = str[0]
		k = str[0]
		for i in range(1, n):
			if str[i] > k:
				break
			l = l + str[i]
			k = str[i]
		if len(l) >= 2 and l[0] == l[1]:
			return l[0] + l[1]
		return l + l[::-1]


import random

class Solution:

	def stringMirror(self, str: str) -> str:
		k = 1
		for i in range(len(str) - 1):
			if str[i] >= str[i + 1] and str[0] != str[1]:
				k += 1
			else:
				break
		x = str[:k] + str[k - 1::-1]
		return x


class Solution:

	def stringMirror(self, str: str) -> str:
		if len(str) >= 2 and str[0] == str[1]:
			return str[0] + str[1]
		i = 1
		while i < len(str) and ord(str[i]) <= ord(str[i - 1]):
			i += 1
		s = str[0:i]
		ans = s[:]
		ans = ans[::-1]
		return s + ans


class Solution:

	def stringMirror(self, st: str) -> str:
		x = st[0]
		m = ''
		m += x
		n = len(st)
		if n == 1:
			return st + st[::-1]
		if n > 1:
			for i in range(1, n):
				if st[0] == st[1]:
					break
				if ord(st[i]) <= ord(st[i - 1]):
					x = st[i]
					m += x
				else:
					break
			return m + m[::-1]


class Solution:

	@staticmethod
	def stringMirror(str):
		i = 0
		while i < len(str) - 1 and str[i] >= str[i + 1] and (str[0] != str[1]):
			i += 1
		sb = str[:i + 1]
		for j in range(len(sb) - 1, -1, -1):
			sb += sb[j]
		return sb


class Solution:

	@staticmethod
	def stringMirror(str):
		s = ''
		ans = ''
		s += str[0]
		for i in range(1, len(str)):
			if str[i - 1] < str[i]:
				break
			if str[i - 1] > str[i]:
				s += str[i]
			if str[i - 1] == str[i] and i - 1 == 0:
				break
			if str[i - 1] == str[i]:
				s += str[i]
		ans += s
		ans += s[::-1]
		return ans


class Solution:

	def stringMirror(self, s: str) -> str:
		sol = [s[0]]
		before = [s[0]]
		n = len(s)
		for i in range(1, n):
			sol.append(s[i])
			rare = sol[::-1]
			r1 = sol + rare
			rare2 = before[::-1]
			r2 = before + rare2
			if r1 <= r2:
				before = sol.copy()
			else:
				return ''.join(before + before[::-1])
		return ''.join(sol + sol[::-1])


class Solution:

	def stringMirror(self, myStr: str) -> str:
		i = 1
		while i < len(myStr) and myStr[i] <= myStr[i - 1]:
			if i == 1 and myStr[i] == myStr[i - 1]:
				break
			i += 1
		return myStr[0:i] + myStr[0:i][::-1]


class Solution:

	def stringMirror(self, s):
		res = tmp = s[0]
		for ch in s[1:]:
			if tmp < ch or ch == s[0]:
				break
			res += ch
			tmp = ch
		return res + res[::-1]


class Solution:

	def stringMirror(self, str: str) -> str:
		left = 1
		l = len(str)
		while left < l and ord(str[left]) <= ord(str[left - 1]):
			if left == 1 and ord(str[left]) == ord(str[left - 1]):
				break
			left += 1
		p = str[:left]
		return p + p[::-1]


class Solution:

	def stringMirror(self, str: str) -> str:
		(temp, res) = ('', '')
		temp += str[0]
		if len(str) == 1 or str[0] <= str[1]:
			temp += str[0]
			return temp
		for i in range(1, len(str)):
			if str[i] <= str[i - 1]:
				temp += str[i]
			else:
				break
		res += temp
		res += temp[::-1]
		return res


class Solution:

	def stringMirror(self, str: str) -> str:
		temp = ''
		last = 'z'
		if len(str) == 1 or str[0] == str[1]:
			return str[0] * 2
		for i in str:
			if i <= last:
				temp = temp + i
				last = i
			else:
				break
		return temp + temp[::-1]