Given a string s, find lexicographically previous permutation of it.
For example: Lexicographically previous permutation of “4321” is “4312". If the string is sorted in ascending order, then the lexicographically previous permutation doesn’t exist.
Example 1:
Input: s = "4321"
Output: "4312" 
Explanation: lexicographically previous
permutation of “4321” is “4312”
Example 2:
Input: s = "1234"
Output: "None"
Explanation: "1234" is sorted in
ascending order, hence "None". 
Your Task:  
You dont need to read input or print anything. Complete the function prevPermutation() which takes string s as input parameter and returns lexicographically previous permutation of s and if there is no lexicographically previous permutation of s, it returns "None".
Expected Time Complexity: O(|s|)
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ |s| ≤ 10^{3}

Source: geeksforgeeks | Difficulty: EASY
Tags: String algorithms

Combinatorics

Data structures

Starter code: #User function Template for python3
class Solution:
	def prevPermutation(self, s):
		# code here


Solutions:
class Solution:

	def prevPermutation(self, s):
		s = [int(i) for i in s]
		inversion_point = len(s) - 2
		while inversion_point >= 0 and s[inversion_point] <= s[inversion_point + 1]:
			inversion_point -= 1
		if inversion_point == -1:
			return None
		for i in reversed(range(inversion_point + 1, len(s))):
			if s[i] < s[inversion_point]:
				(s[inversion_point], s[i]) = (s[i], s[inversion_point])
				break
		s[inversion_point + 1:] = s[:inversion_point:-1]
		s = [str(i) for i in s]
		return ''.join(s)


class Solution:

	def prevPermutation(self, s):
		arr = list(s)
		for i in reversed(range(len(arr) - 1)):
			if int(arr[i]) > int(arr[i + 1]):
				j = i + 1
				while j < len(arr) and int(arr[i]) > int(arr[j]):
					j += 1
				(arr[i], arr[j - 1]) = (arr[j - 1], arr[i])
				i += 1
				j = len(arr)
				while i < j - 1:
					(arr[i], arr[j - 1]) = (arr[j - 1], arr[i])
					i += 1
					j -= 1
				return ''.join(arr)
		return


class Solution:

	def prevPermutation(self, s):
		s = list(s)
		i = len(s) - 1
		while i > 0 and s[i - 1] <= s[i]:
			i -= 1
		if i == 0:
			return None
		index = i - 1
		i = len(s) - 1
		while s[i] >= s[index]:
			i -= 1
		(s[i], s[index]) = (s[index], s[i])
		s = s[:index + 1] + s[index + 1:][::-1]
		s = ''.join(s)
		return s


class Solution:

	def prevPermutation(self, s):
		n = len(s)
		f = 0
		for i in range(n - 1, 0, -1):
			if s[i - 1] > s[i]:
				p = i - 1
				f = 1
				break
		if f == 0:
			return 'None'
		for i in range(n - 1, p, -1):
			if s[i] < s[p]:
				m = i
				break
		l = []
		for i in s:
			l.append(i)
		(l[m], l[p]) = (l[p], l[m])
		l[p + 1:] = l[n - 1:p:-1]
		return ''.join(l)


class Solution:

	def prevPermutation(self, s):
		start = -1
		length = len(s)
		for i in range(length - 1, 0, -1):
			if s[i] < s[i - 1]:
				start = i - 1
				break
		if start == -1:
			return None
		sorted_part = sorted(s[start:], reverse=True)
		sorted_length = len(sorted_part)
		second_string_part = ''
		replace = ''
		added_once = False
		for i in range(sorted_length - 1, -1, -1):
			if i == 0 or sorted_part[i - 1] != s[start] or added_once:
				second_string_part = sorted_part[i] + second_string_part
			else:
				replace = sorted_part[i]
				added_once = True
		return s[:start] + replace + second_string_part


class Solution:

	def prevPermutation(self, s):
		arr = list(s)
		i = len(arr) - 1
		idx = -1
		while i > 0:
			if arr[i - 1] > arr[i]:
				idx = i
				break
			else:
				i -= 1
		if idx == -1:
			return 'None'
		small = idx
		for x in range(idx + 1, len(arr)):
			if arr[x] < arr[idx - 1]:
				small = x
		(arr[idx - 1], arr[small]) = (arr[small], arr[idx - 1])
		(m, n) = (idx, len(arr) - 1)
		while m <= n:
			(arr[m], arr[n]) = (arr[n], arr[m])
			m += 1
			n -= 1
		return ''.join(arr)


class Solution:

	def prevPermutation(self, s):
		p = len(s) - 2
		s = list(s)
		while p >= 0:
			if s[p] <= s[p + 1]:
				p -= 1
				continue
			break
		if p == -1:
			return ''.join(s)[::-1]
		for i in range(len(s) - 1, p, -1):
			if s[p] > s[i]:
				break
		(s[p], s[i]) = (s[i], s[p])
		rev = s[p + 1:]
		rev.reverse()
		s[p + 1:] = rev
		return ''.join(s)


class Solution:

	def prevPermutation(self, s):
		l = []
		m = -1
		for i in s:
			l.append(i)
		for i in range(1, len(l)):
			if l[i - 1] > l[i]:
				m = i - 1
		if m == -1:
			return s
		for i in range(m + 1, len(s)):
			if l[m] > l[i]:
				x = i
		(l[m], l[x]) = (l[x], l[m])
		(i, j) = (m + 1, len(l) - 1)
		while j > i:
			(l[i], l[j]) = (l[j], l[i])
			i = i + 1
			j = j - 1
		return ''.join(l)


class Solution:

	def prevPermutation(self, a):
		n = len(a)
		res = ''
		for i in range(n - 1, 0, -1):
			if a[i] < a[i - 1]:
				found = i - 1
				temp_idx = -1
				for j in range(n - 1, i - 1, -1):
					if a[j] < a[found]:
						temp_idx = j
						break
				res += a[:found] + a[temp_idx] + a[n - 1:temp_idx:-1] + a[found] + a[temp_idx - 1:found:-1]
				break
		return res if res else 'None'


class Solution:

	def reverse(self, l, ind1, ind2):
		while ind1 < ind2:
			(l[ind1], l[ind2]) = (l[ind2], l[ind1])
			ind1 += 1
			ind2 -= 1

	def prevPermutation(self, arr):
		l = list(s)
		n = len(s)
		(ind1, ind2) = (-1, -1)
		for i in range(n - 2, -1, -1):
			if arr[i] > arr[i + 1]:
				ind1 = i
				break
		for i in range(n - 1, 0, -1):
			if arr[ind1] > arr[i]:
				ind2 = i
				break
		if ind1 == -1 or ind2 == -1:
			return 'None'
		(l[ind1], l[ind2]) = (l[ind2], l[ind1])
		self.reverse(l, ind1 + 1, n - 1)
		return ''.join(l)


class Solution:

	def prevPermutation(self, s):
		flag = 0
		for i in range(1, len(s)):
			if s[i] < s[i - 1]:
				m = i - 1
				flag = 1
		if flag == 0:
			return 'None'
		l = [i for i in s]
		for i in range(m + 1, len(s)):
			if s[m] > s[i]:
				k = i
		(l[m], l[k]) = (l[k], l[m])
		(i, j) = (m + 1, len(s) - 1)
		while j > i:
			(l[i], l[j]) = (l[j], l[i])
			i = i + 1
			j = j - 1
		return ''.join(l)


class Solution:

	def prevPermutation(self, arr):
		arr = list(arr)
		i = len(arr) - 1
		while i > 0 and arr[i] >= arr[i - 1]:
			i -= 1
		if i == 0:
			return None
		j = len(arr) - 1
		k = i - 1
		while arr[j] >= arr[k]:
			j -= 1
		(arr[j], arr[k]) = (arr[k], arr[j])
		l = k + 1
		r = len(arr) - 1
		while l < r:
			(arr[l], arr[r]) = (arr[r], arr[l])
			l += 1
			r -= 1
		return ''.join(arr)