Given a string S consisting of only lowercase characters. Find the lexicographically smallest string after removing exactly k characters from the string. But you have to correct the value of k, i.e., if the length of the string is a power of 2, reduce k by half, else multiply k by 2. You can remove any k character.
NOTE: If it is not possible to remove k (the value of k after correction) characters or if the resulting string is empty return -1. 
Example 1:
Input: S = "fooland", k = 2
Output: "and" 
Explanation: As the size of the string = 7
which is not a power of 2, hence k = 4.
After removing 4 characters from the given 
string, the lexicographically smallest
string is "and".
Example 2:
Input: S = "code", k = 4
Output: "cd"
Explanation: As the length of the string = 4, 
which is 2 to the power 2, hence k = 2.
Hence, lexicographically smallest string after 
removal of 2 characters is "cd".
Your Task:  
You dont need to read input or print anything. Complete the function lexicographicallySmallest() which takes S and k as input parameters and returns the lexicographically smallest string after removing k characters.
Expected Time Complexity: O(n+k), n is size of the string
Expected Auxiliary Space: O(n)
Constraints:
1<= |S| <=10^{5}
1<= k <= 10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: String algorithms

Data structures

Starter code: #User function Template for python3

class Solution:

    def lexicographicallySmallest (ob, S, k):

        # code here 

Solutions:
from collections import deque

class Solution:

	def ispower(ob, k):
		return True if k & k - 1 == 0 else False

	def lexicographicallySmallest(ob, S, k):
		st = deque()
		top = -1
		n = len(S)
		k = k // 2 if ob.ispower(n) else 2 * k
		if k >= n:
			return '-1'
		ans = ''
		for ch in S:
			while k > 0 and top >= 0 and (ch < st[top]):
				st.pop()
				k -= 1
				top -= 1
			st.append(ch)
			top += 1
		while k > 0 and top != -1:
			st.pop()
			top -= 1
			k -= 1
		while top >= 0:
			ans = st.pop() + ans
			top -= 1
		return ans


from math import log2

class Solution:

	def lexicographicallySmallest(ob, S, k):
		n = len(S)
		if log2(n) == int(log2(n)):
			k = k // 2
		else:
			k = k * 2
		if k >= n:
			return -1
		stack = []
		for item in S:
			while k and stack and (stack[-1] > item):
				stack.pop()
				k -= 1
			stack.append(item)
		return ''.join(stack[:len(stack) - k])


class Solution:

	def lexicographicallySmallest(ob, S, k):
		ans = ''
		l = len(S)
		if l & l - 1:
			k += k
		else:
			k //= 2
		if k >= l:
			return '-1'
		st = []
		for i in range(l):
			while st and k > 0 and (st[-1] > S[i]):
				st.pop()
				k -= 1
			st.append(S[i])
		if k > 0:
			while k > 0:
				st.pop()
				k -= 1
		while st:
			ans = st[-1] + ans
			st.pop()
		return ans


class Solution:

	def power2(self, n):
		return n & n - 1 == 0

	def lexicographicallySmallest(self, S, k):
		n = len(S)
		k = k // 2 if self.power2(n) else k * 2
		if k >= n:
			return '-1'
		s = []
		num = k
		for c in S:
			while len(s) > 0 and c < s[-1] and (num > 0):
				s.pop()
				num -= 1
			s.append(c)
		while len(s) > n - k:
			s.pop()
		return ''.join(s)


class Solution:

	def lexicographicallySmallest(ob, S, k):
		n = len(S)
		if n & ~(n - 1) == n:
			k = k // 2
		else:
			k = k * 2
		if k > n:
			return -1
		stack = []
		for i in S:
			if len(stack) == 0:
				stack.append(i)
			elif ord(stack[-1]) < ord(i):
				stack.append(i)
			else:
				while k > 0 and len(stack) != 0 and (ord(stack[-1]) > ord(i)):
					stack.pop(-1)
					k -= 1
				stack.append(i)
		while k > 0 and len(stack) != 0:
			stack.pop(-1)
			k -= 1
		if len(stack) == 0:
			return -1
		return ''.join(stack)


class Solution:

	def lexicographicallySmallest(ob, S, k):
		n = len(S)
		a = k
		if n == 1 or n == 2:
			k = k // 2
		x = 2
		if n > 1:
			while x < n + 1:
				x = x * 2
				if x == n:
					k = k // 2
		if k == a:
			k = k * 2
		if k >= n:
			return -1
		elif k < n:
			stack = [S[0]]
			for i in range(1, n):
				while k > 0 and stack and (stack[-1] > S[i]):
					stack.pop()
					k -= 1
				stack.append(S[i])
			while stack and k > 0:
				stack.pop()
				k -= 1
			ans = ''
			while len(stack) > 0:
				ans += stack[-1]
				stack.pop()
		return ans[::-1]


class Solution:

	def lexicographicallySmallest(ob, S, k):
		n = len(S)
		flag = True
		k = k // 2 if n & n - 1 == 0 else k * 2
		if k >= n:
			return -1
		if k == 0:
			return S
		st = []
		for i in range(n):
			while k > 0 and len(st) > 0 and (S[i] < st[-1]):
				st.pop()
				k -= 1
			st.append(S[i])
		st = st[:len(st) - k]
		return ''.join(st)


import math

class Solution:

	def lexicographicallySmallest(ob, S, k):
		n = len(S)
		setti = set([2 ** i for i in range(20)])
		if n in setti:
			k = k // 2
		else:
			k = k * 2
		if k >= n:
			return -1
		stack = []
		arr = [*S][::-1]
		while k:
			if not stack:
				stack.append(arr.pop())
			elif not arr:
				return ''.join(stack[:-k])
			elif ord(stack[-1]) > ord(arr[-1]):
				stack.pop()
				k -= 1
			else:
				stack.append(arr.pop())
		return ''.join(stack + arr[::-1])


class Solution:

	def lexicographicallySmallest(ob, s, k):
		count = 0
		l = len(s)
		if l & l - 1:
			k += k
		else:
			k //= 2
		if k >= l:
			return '-1'
		stack = []
		for i in range(len(s)):
			while stack and k > 0 and (ord(stack[-1]) > ord(s[i])):
				stack.pop()
				k -= 1
			stack.append(s[i])
		while k > 0 and stack:
			stack.pop()
			k -= 1
		return ''.join(stack) if stack else '-1'


class Solution:

	def lexicographicallySmallest(ob, s, k):
		n = len(s)
		if n & n - 1 == 0:
			k = k // 2
		else:
			k = 2 * k
		if k > n:
			return -1
		stack = []
		for ch in s:
			while stack and ord(ch) < ord(stack[-1]) and (k != 0):
				stack.pop()
				k -= 1
			stack.append(ch)
		while k != 0:
			stack.pop()
			k -= 1
		return ''.join(stack) if len(stack) > 0 else -1


import math

class Solution:

	def lexicographicallySmallest(ob, s, k):
		n = len(s)
		if n & n - 1:
			k += k
		else:
			k //= 2
		if k >= n:
			return -1
		st = []
		ans = ''
		for i in range(n):
			while st and k > 0 and (st[-1] > s[i]):
				st.pop()
				k -= 1
			st.append(s[i])
		if k > 0:
			while k > 0:
				st.pop()
				k -= 1
		while st:
			ans = st[-1] + ans
			st.pop()
		return ans


class Solution:

	def lexicographicallySmallest(ob, S, k):
		n = len(S)

		def isPow(n):
			return n & n - 1
		if isPow(n):
			k = k * 2
		else:
			k = k // 2
		if k >= n:
			return '-1'
		st = []
		res = ''
		j = 0
		while j < n:
			while st and S[j] < st[-1] and (k != 0):
				st.pop()
				k -= 1
			st.append(S[j])
			j += 1
		while k > 0:
			if st:
				st.pop()
			else:
				return -1
			k -= 1
		if st:
			return res.join(st)
		else:
			return '-1'


class Solution:

	def lexicographicallySmallest(ob, S, k):
		l = len(S)
		f = 0
		while l % 2 == 0:
			l /= 2
		if l == 1:
			f = 1
		if f:
			k //= 2
		else:
			k *= 2
		if len(S) <= k:
			return -1
		stack = []
		cnt = 0
		for s in S:
			while cnt < k and len(stack) > 0 and (stack[-1] > s):
				stack.pop()
				cnt += 1
			stack.append(s)
		while cnt < k:
			stack.pop()
			cnt += 1
		return ''.join(stack)


import math
from collections import deque

class Solution:

	def lexicographicallySmallest(ob, S, k):
		n = len(S)
		if math.ceil(math.log2(n)) == math.floor(math.log2(n)):
			k = k // 2
		else:
			k = k * 2
		if k >= len(S):
			return -1
		st = deque()
		for i in range(len(S)):
			while st and ord(st[-1]) > ord(S[i]) and (k > 0):
				st.pop()
				k = k - 1
			st.append(S[i])
		while k > 0 and st:
			st.pop()
			k = k - 1
		string = ''
		for i in range(len(st)):
			string += st.pop()
		string = string[::-1]
		return string


class Solution:

	def lexicographicallySmallest(ob, S, k):
		n = len(S)
		if n & n - 1 == 0:
			k //= 2
		else:
			k *= 2
		if k >= n:
			return -1
		need_len = n - k
		cur_ans = None
		stack = []
		for i in range(n):
			while stack and k and (stack[-1] > S[i]):
				stack.pop()
				k -= 1
			stack.append(S[i])
		while k:
			stack.pop()
			k -= 1
		return ''.join(stack)


class Solution:

	def lexicographicallySmallest(ob, S, k):
		n = len(S)

		def power2(n):
			if n == 1:
				return True
			elif n % 2 != 0 or n == 0:
				return False
			return power2(n / 2)
		if power2(n):
			k = k // 2
		else:
			k = k * 2
		if k >= n:
			return '-1'
		st = []
		for i in range(n):
			while st and k > 0 and (st[-1] > S[i]):
				st.pop()
				k = k - 1
			st.append(S[i])
		while k > 0 and st:
			st.pop()
			k = k - 1
		ans = ''
		for i in range(len(st)):
			ans = ans + st[i]
		return ans


from collections import deque

class Solution:

	def lexicographicallySmallest(ob, S, k):

		def power(n):
			while n % 2 == 0:
				n //= 2
			if n == 1:
				return True
			return False
		if power(len(S)):
			k //= 2
		else:
			k *= 2
		if len(S) <= k:
			return -1
		stk = deque([])
		cnt = 0
		i = 0
		while i < len(S):
			ele = S[i]
			while stk and stk[-1] > ele and (cnt < k):
				cnt += 1
				stk.pop()
			stk.append(ele)
			i += 1
		if cnt < k:
			while stk and cnt < k:
				stk.pop()
				cnt += 1
		ans = ''
		while stk:
			ans += stk.pop()
		return ans[::-1]


import math

class Solution:

	def lexicographicallySmallest(ob, S, k):
		n = len(S)
		if n & n - 1 == 0:
			k = k // 2
		else:
			k = k * 2
		stack = []
		if k > len(S):
			return -1
		for i in range(len(S)):
			while stack and stack[-1] > S[i] and (k > 0):
				stack.pop()
				k -= 1
			stack.append(S[i])
		if k > 0:
			while k > 0:
				stack.pop()
				k -= 1
		return ''.join(stack) if stack else -1


from math import log2

class Solution:

	def lexicographicallySmallest(ob, S, k):
		if log2(len(S)) == int(log2(len(S))):
			k = k // 2
		else:
			k = k * 2
		if len(S) <= k:
			return -1
		s = []
		size = len(S) - k
		for i in range(len(S)):
			c = S[i]
			while s and s[-1] > c and (len(S) - i > size - len(s)):
				s.pop()
			if size - len(s) > 0:
				s.append(c)
		return ''.join((c for c in s))


class Solution:

	def lexicographicallySmallest(ob, s, k):
		n = len(s)
		if n and (not n & n - 1):
			k = k // 2
		else:
			k = k * 2
		if k >= n:
			return -1
		stack = []
		for i in range(n):
			while stack and k and (s[i] < stack[-1]):
				stack.pop()
				k -= 1
			stack.append(s[i])
		while stack and k:
			stack.pop()
			k -= 1
		return ''.join(stack)


class Solution:

	def lexicographicallySmallest(ob, s, k):
		sl = []
		l = len(s)
		if l & l - 1:
			k *= 2
		else:
			k //= 2
		if k >= l:
			return -1
		for i in range(l):
			while sl and k > 0 and (s[i] < sl[-1]):
				sl.pop()
				k -= 1
			sl.append(s[i])
		while k > 0 and sl:
			sl.pop()
			k -= 1
		_s_ = ''
		while sl:
			_s_ += sl.pop()
		return _s_[::-1]


class Solution:

	def lexicographicallySmallest(ob, S, k):
		if len(S) & len(S) - 1 == 0:
			k = k // 2
		else:
			k = k * 2
		stack = []
		removed_count = 0
		if k >= len(S):
			return -1
		for i in range(len(S)):
			while len(stack) != 0 and stack[-1] > S[i] and (removed_count < k):
				stack.pop(-1)
				removed_count += 1
			stack.append(S[i])
		while removed_count < k and len(stack) != 0:
			stack.pop(-1)
			removed_count += 1
		if len(stack) == 0:
			return -1
		answer = ''.join(stack)
		return answer


class Solution:

	def lexicographicallySmallest(ob, S, k):
		l = len(S)
		if l & l - 1 == 0:
			k = k // 2
		else:
			k = k * 2
		if len(S) == 1 or k > len(S):
			return -1
		stack = [S[0]]
		start = 1
		while k > 0 and start < len(S):
			if S[start] >= stack[-1]:
				stack.append(S[start])
				start += 1
			else:
				while k > 0 and len(stack) > 0 and (S[start] < stack[-1]):
					stack.pop()
					k -= 1
				stack.append(S[start])
				start += 1
		while k > 0:
			stack.pop()
			k -= 1
		return ''.join(stack) + S[start:]


class Solution:

	def lexicographicallySmallest(ob, S, K):
		N = len(S)
		K = K * 2 if N & N - 1 else K // 2
		if K >= N:
			return -1
		(st, rem) = ('', 0)
		for c in S:
			while st and rem < K and (st[-1] > c):
				st = st[:-1]
				rem += 1
			st += c
		return st[:N - K]


class Solution:

	def powOfTwo(self, n):
		if n < 1:
			return False
		if n == 1:
			return True
		return self.powOfTwo(n / 2)

	def lexicographicallySmallest(self, S, k):
		n = len(S)
		isPowOfTwo = False
		if n > 1:
			isPowOfTwo = self.powOfTwo(n)
		if isPowOfTwo:
			k = int(k / 2)
		else:
			k = k * 2
		if k >= n:
			return -1
		stk = []
		for c in S:
			while len(stk) > 0 and stk[-1] > c and (k > 0):
				stk.pop()
				k -= 1
			stk.append(c)
		while k > 0 and len(stk) > 0:
			stk.pop()
			k -= 1
		return ''.join(stk)


class Solution:

	def lexicographicallySmallest(ob, S, k):
		sol = []
		l = len(S)
		if l & l - 1:
			k += k
		else:
			k //= 2
		if k >= l:
			return '-1'
		parts = []
		for i in range(l):
			while parts and k > 0 and (parts[-1] > S[i]):
				parts.pop()
				k -= 1
			parts.append(S[i])
		while k > 0:
			parts.pop()
			k -= 1
		while parts:
			sol.append(parts[-1])
			parts.pop()
		return ''.join(sol[::-1])


class Solution:

	def is2pow(ob, s):
		n = len(s)
		return n and (not n & n - 1)

	def lexicographicallySmallest(ob, S, k):
		if ob.is2pow(S):
			k = k // 2
		else:
			k = k * 2
		if k >= len(S):
			return -1
		if k == 0:
			return S
		stack = []
		for char in S:
			while stack and k > 0 and (stack[-1] > char):
				stack.pop()
				k -= 1
			stack.append(char)
		stack = stack[:len(stack) - k]
		return ''.join(stack)


from math import floor

class Solution:

	def lexicographicallySmallest(ob, S, k):
		if len(S) & len(S) - 1 == 0:
			k = floor(k / 2)
		else:
			k = k * 2
		if k > len(S):
			return -1
		ls = []
		for i in S:
			if len(ls) == 0 or ls[-1] <= i or k == 0:
				ls.append(i)
			else:
				while len(ls) != 0 and ls[-1] > i and (k != 0):
					ls.pop()
					k = k - 1
				ls.append(i)
		if k != 0:
			if len(ls) <= k:
				return -1
			else:
				while k != 0:
					ls.pop()
					k = k - 1
				return ''.join(ls)
		else:
			return ''.join(ls)


class Solution:

	def lexicographicallySmallest(ob, S, k):
		size = len(S)
		k = k // 2 if size & size - 1 == 0 else k * 2
		if k >= size:
			return -1
		elif k == 0:
			return S
		else:
			stack = []
			for char in S:
				while stack and k > 0 and (stack[-1] > char):
					stack.pop()
					k -= 1
				stack.append(char)
			stack = stack[:len(stack) - k]
			return ''.join(stack)


import math

class Solution:

	def lexicographicallySmallest(ob, S, k):
		if math.log2(len(S)) == int(math.log2(len(S))):
			k //= 2
		else:
			k *= 2
		if k > len(S):
			return -1
		stack = []
		for i in range(len(S)):
			while stack and k > 0:
				if stack[-1] > S[i]:
					stack.pop()
					k -= 1
				else:
					break
			stack.append(S[i])
		while k > 0:
			stack.pop()
			k -= 1
		p = ''.join(stack)
		if len(p) == 0:
			return -1
		return p


import math

class Solution:

	def lexicographicallySmallest(ob, s, k):
		n = len(s)
		t = math.log(n, 2)
		t1 = int(t)
		if t1 < t:
			k *= 2
		else:
			k = k // 2
		if k >= len(s):
			return -1
		if k == 0:
			return s
		q = []
		s = list(s)
		for i in range(n):
			while q and k > 0 and (q[-1] > s[i]):
				q.pop()
				k -= 1
			q.append(s[i])
		while q and k > 0:
			q.pop()
			k -= 1
		if k > 0:
			return -1
		output = ''.join(q)
		return output


class Solution:

	def lexicographicallySmallest(ob, S, k):
		if len(S) == 1 and k > 1:
			return -1
		l = len(S)
		bn = bin(l)
		if bn.count('1') == 1:
			k = k // 2
		else:
			k = k * 2
		if k > len(S):
			return -1
		stack = []
		for i in range(len(S)):
			while stack and stack[-1] > S[i] and (k > 0):
				stack.pop()
				k -= 1
			stack.append(S[i])
		if k != 0:
			ls = len(stack) - k
			stack = stack[:ls]
			return ''.join(stack)
		else:
			return ''.join(stack)


def isPowerOfTwo(x):
	return x and (not x & x - 1)

class Solution:

	def lexicographicallySmallest(ob, S, k):
		if isPowerOfTwo(len(S)):
			k //= 2
		else:
			k *= 2
		if k >= len(S):
			return -1
		m = []
		for i in S:
			while len(m) > 0 and m[-1] > i and (k > 0):
				m.pop()
				k -= 1
			m.append(i)
		while k > 0:
			m.pop()
			k -= 1
		return ''.join(m)


class Solution:

	def lexicographicallySmallest(ob, S, k):
		n = len(S)
		if n == 0:
			return -1
		if n & n - 1 != 0:
			k *= 2
		else:
			k = k // 2
		if k >= n:
			return -1
		s = []
		K = k
		idx = 0
		for i in range(len(S)):
			while s and k > 0 and (ord(s[-1]) > ord(S[i])):
				s.pop()
				k -= 1
			if k == 0:
				break
			idx += 1
			s.append(S[i])
		return ''.join(s + list(S[idx:]))[:n - K]


class Solution:

	def lexicographicallySmallest(ob, S, k):
		p = 2
		z = 0
		while p <= len(S):
			if len(S) == p:
				k = k // 2
				z = 1
				break
			p *= 2
		if z == 0:
			k = k * 2
		if len(S) <= k:
			return -1
		else:
			i = 1
			stack = []
			top = 0
			stack.append(S[0])
			while k > 0 and i < len(S):
				if top == -1:
					stack.append(S[i])
					top += 1
					i += 1
				elif stack[top] > S[i]:
					stack.pop()
					k -= 1
					top -= 1
					continue
				else:
					stack.append(S[i])
					top += 1
					i += 1
			if k == 0:
				for m in range(i, len(S)):
					stack.append(S[m])
			res = ''
			for ele in stack:
				res += ele
			if k > 0:
				return res[:len(res) - k]
			return res


class Solution:

	def lexicographicallySmallest(ob, S, k):
		n = len(S)
		if n and (not n & n - 1):
			k = k // 2
		else:
			k = k * 2
		if k >= len(S):
			return '-1'
		x = n - k
		s1 = []
		for i in range(0, n):
			while s1 and S[i] < s1[-1] and (len(s1) + n - i > x):
				s1.pop()
			s1.append(S[i])
		ans = ''
		for i in range(0, x):
			ans += s1[i]
		return ans


class Solution:

	def lexicographicallySmallest(ob, S, k):
		l = len(S)
		if l & l - 1:
			k *= 2
		else:
			k //= 2
		if k >= l:
			return -1
		st = []
		for i in S:
			while st and k and (st[-1] > i):
				st.pop()
				k -= 1
			st.append(i)
		while st and k:
			st.pop()
			k -= 1
		return ''.join(st)


from collections import deque

class Solution:

	def lexicographicallySmallest(ob, S, k):
		l = len(S)
		if l & l - 1 == 0:
			k = k // 2
		else:
			k = k * 2
		if k >= l:
			return -1
		else:
			q = deque()
			q.append(S[0])
			i = 1
			n = 1
			while k > 0 and i < l:
				if S[i] >= q[-1]:
					q.append(S[i])
					i += 1
					n += 1
				else:
					while S[i] < q[-1]:
						q.pop()
						k -= 1
						n -= 1
						if k == 0:
							break
						if n == 0:
							q.append(S[i])
							i += 1
							n += 1
			if k == 0 and n == 0:
				ans = S[i:]
				return ans
			elif k == 0 and n != 0:
				ans = ''
				for j in q:
					ans += j
				ans += S[i:]
				return ans
			else:
				while k != 0:
					if q[0] >= q[-1]:
						q.popleft()
						k -= 1
					else:
						q.pop()
						k -= 1
				ans = ''
				for i in q:
					ans += i
				return ans