Given an string S, representing a large interger. Return the largest-valued odd integer (as a string) that is substring of the given string S.
Note : A substring is a contiguous sequence of characters within a string. Null string ("") is also a substring.
Example 1:
Input: s = "504"
Output: "5"
Explanation: The only subtring "5" is odd number.
 
Example 2:
Input: s = "2042"
Output: ""
Explanation: All the possible non-empty substring have even value.
 
Your Task:
You don't need to read input or print anything. Your task is to complete the function maxOdd() which takes the string S as input and returns the largest-valued odd integer that is substring of the given string.
Expected Time Complexity: O(|S|).
Expected Auxiliary Space: O(1).
Constraints:
1<=|S|<=2*10^{5}
S only consists of digits and does not contain any leading zeros.

Difficulty: EASY
Tags: String algorithms

Data structures
Skill types: Data structures
Expected Time Complexity: O(|S|).
Expected Auxiliary Space: O(1).

Starter code:
#User function Template for python3



class Solution:

    def maxOdd(self, s):

Solutions:
class Solution:

	def maxOdd(self, s):
		for i in range(len(s) - 1, -1, -1):
			if s[i] in {'1', '3', '5', '7', '9'}:
				return s[:i + 1]
		return ''


import sys

class Solution:

	def maxOdd(self, s):
		ss = s[::-1]
		for i in range(len(ss)):
			if int(ss[i]) % 2 != 0:
				sss = ss[i:]
				return sss[::-1]
		return ''


class Solution:

	def maxOdd(self, s):
		end = -1
		start = 0
		for i in range(0, len(s)):
			if int(s[i]) % 2 != 0:
				end = i
		if end == -1:
			return ''
		return s[start:end + 1]


class Solution:

	def maxOdd(self, s):
		n = len(s) - 1
		while n >= 0:
			if int(s[n]) % 2 != 0:
				return s[:n + 1]
			n -= 1
		return ''


class Solution:

	def maxOdd(self, num):
		op = []
		for i in range(len(num)):
			if int(num[i]) % 2 != 0:
				op.append(i)
			else:
				pass
		if len(op) == 0:
			return ''
		elif op[-1] == len(num) - 1:
			return num
		else:
			return ''.join(num[:op[-1] + 1])


class Solution:

	def maxOdd(self, s):
		l = list(map(int, s))
		st = 0
		t = 0
		for i in range(len(l)):
			if l[i] % 2 != 0:
				t = 1
				st = i
		if t == 0:
			return ''
		return s[:st + 1]


class Solution:

	def maxOdd(self, s):
		ch = 0
		for i in s:
			if int(i) % 2 != 0:
				ch = 1
		if ch == 0:
			return ''
		else:
			for i in range(len(s) - 1, -1, -1):
				if int(s[i]) % 2 != 0:
					return int(s[:i + 1])


class Solution:

	def maxOdd(self, s):
		ma = 0
		for i in range(len(s), -0, -1):
			if int(s[0:i]) % 2 == 1:
				ma = max(ma, int(s[0:i]))
		if ma == 0:
			return ''
		return ma


class Solution:

	def maxOdd(self, S):
		end = None
		for i in range(len(S) - 1, -1, -1):
			if int(S[i]) % 2 != 0:
				end = i
				break
		if end is not None:
			return S[:end + 1]
		return ''


class Solution:

	def maxOdd(self, num):
		if float(num) % 2 != 0:
			return num
		else:
			n = int(num)
			for i in range(len(num)):
				if n % 2 != 0:
					return str(n)
				else:
					n //= 10
		return ''


class Solution:

	def maxOdd(self, s):
		s = s[::-1]
		j = 0
		for i in range(len(s)):
			if int(s[i]) % 2 != 0:
				j = i
				break
		if j == 0 and int(s[0]) % 2 == 0:
			return ''
		else:
			n = len(s) - j - 1
			s = s[::-1]
			f = s[:n + 1]
			return f


class Solution:

	def maxOdd(self, s):
		n = len(s)
		for i in range(n - 1, -1, -1):
			if int(s[i]) % 2 == 1:
				return s[:i + 1]
		return ''


class Solution:

	def maxOdd(self, S):
		for i in range(len(S) - 1, -1, -1):
			if int(S[i]) % 2:
				return S[:i + 1]
		return ''


class Solution:

	def maxOdd(self, s):
		while 1:
			if int(s) % 2 == 1:
				return s
			else:
				s = s[:-1]
			if len(s) == 0:
				break
		return ''


class Solution:

	def maxOdd(self, s):
		strlen = len(s) - 1
		while strlen >= 0:
			c = int(s[strlen])
			if c % 2 != 0:
				return s[0:strlen + 1]
			strlen -= 1
		return ''


class Solution:

	def maxOdd(self, s):
		odd = -1
		for (i, el) in enumerate(s):
			if el != 0 and int(el) % 2 != 0:
				odd = i
		if odd == -1:
			return ''
		return s[:odd + 1]


class Solution:

	def maxOdd(self, s):
		ptr1 = 0
		ptr2 = len(s)
		while ptr1 < ptr2:
			if int(s[ptr1:ptr2]) % 2 != 0:
				return s[ptr1:ptr2]
			else:
				ptr2 -= 1
		return ''


class Solution:

	def maxOdd(self, s):
		p = -1
		for i in range(len(s) - 1, -1, -1):
			if int(s[i]) & 1:
				p = i
				break
		if p == -1:
			return ''
		return s[:p + 1]


class Solution:

	def maxOdd(self, s):
		new = ''
		n = len(s)
		for i in range(n - 1, -1, -1):
			if len(new) != 0:
				new = s[i] + new
			if len(new) == 0:
				if s[i] == '1' or s[i] == '3' or s[i] == '5' or (s[i] == '7') or (s[i] == '9'):
					new = s[i] + new
		return new


class Solution:

	def maxOdd(self, s):
		max = 0
		if int(s) % 2 != 0:
			return s
		s1 = ''
		for i in s:
			s1 = s1 + i
			j = int(s1)
			if j % 2 != 0:
				if j > max:
					max = j
			if j % 2 == 0:
				continue
		if max:
			max = str(max)
			return max
		else:
			return ''


class Solution:

	def maxOdd(self, s):
		p = ''
		l = 0
		for i in range(0, len(s)):
			p += s[i]
			p = int(p)
			if p % 2 != 0:
				l = p
			p = str(p)
		if l > 0:
			return l
		k = ''
		return k


class Solution:

	def maxOdd(self, s):
		a = s.split(' ')
		e = []
		o = []
		for i in range(len(s) - 1, -1, -1):
			if int(s[i]) % 2 != 0:
				return s[0:i + 1:1]
				print(s)
		return ''


class Solution:

	def maxOdd(self, s):
		if int(s) % 2 != 0:
			return s
		q = []
		for i in range(len(s)):
			m = s[:i + 1]
			if int(m) % 2 != 0:
				q.append(m)
		if not q:
			return ''
		return max([int(i) for i in q])


class Solution:

	def maxOdd(self, s):
		mx = 0
		for i in range(len(s) - 1, -1, -1):
			a = int(s[i])
			if a % 2:
				return s[:i + 1]
		return ''


class Solution:

	def maxOdd(self, s):
		for i in range(len(s) - 1, -1, -1):
			num = int(s[i])
			if num & 1 != 0:
				return s[0:i + 1]
		return ''


class Solution:

	def maxOdd(self, s):
		ans = ''
		tmp = ''
		for i in s:
			tmp += i
			if int(tmp) % 2 != 0:
				ans = tmp
		return ans


class Solution:

	def maxOdd(self, s):
		res = ''
		cur = ''
		for i in s:
			if int(i) % 2 != 0:
				cur += i
				res = max(res, cur)
			else:
				cur += i
		return res


class Solution:

	def maxOdd(self, num):
		indx = -1
		n = len(num)
		for i in range(n):
			if int(num[i]) % 2 == 1:
				indx = i
		if indx == -1:
			return ''
		return num[:indx + 1]


class Solution:

	def maxOdd(self, s):
		for i in range(len(s) - 1, -1, -1):
			if s[i] in '13579':
				return s[:i + 1]
		return ''


class Solution:

	def maxOdd(self, s):
		maxi = 0
		sbs = ''
		for i in s:
			sbs += i
			if int(sbs) % 2 != 0:
				maxi = max(int(maxi), int(sbs))
		return '' if maxi == 0 else maxi


class Solution:

	def maxOdd(self, s):
		num = int(s)
		st = ''
		for i in range(len(s)):
			remainder = num % 10
			if remainder % 2 != 0:
				st += str(num)
				return st
			num = num // 10
		return st


class Solution:

	def maxOdd(self, s):
		n = int(s)
		if n % 2 != 0:
			return str(n)
		while n != 0:
			n = n // 10
			if n % 2 != 0:
				return str(n)
		else:
			return ''


class Solution:

	def maxOdd(self, s):
		l = 0
		j = len(s) - 1
		while j != -1:
			if int(s[j]) % 2 != 0:
				break
			j -= 1
		return s[:j + 1]


class Solution:

	def maxOdd(self, s):
		out = ''
		max_s = ''
		max = 0
		for i in s:
			out += i
			if max < int(out) and int(out) % 2 == 1:
				max = int(out)
				max_s = out
		return max_s


class Solution:

	def maxOdd(self, s):
		(out, m) = ('', [])
		for e in s:
			out = out + e
			if int(out) % 2 != 0:
				m.append(int(out))
		if len(m) == 0:
			return ''
		return max(m)


class Solution:

	def maxOdd(self, s):
		mo = ''
		st = -1
		en = -1
		for i in range(len(s)):
			if int(s[i]) % 2 != 0 and st == -1:
				st = i
			elif int(s[i]) % 2 != 0:
				en = i
			else:
				continue
		if en == -1:
			en = st
		return s[:en + 1]


class Solution:

	def maxOdd(self, s):
		m = 0
		for i in range(len(s)):
			if int(s[:i + 1]) % 2 != 0 and int(s[:i + 1]) > m:
				m = int(s[:i + 1])
		return str(m) if m > 0 else ''


class Solution:

	def maxOdd(self, s):
		c = -1
		for i in range(len(s) - 1, -1, -1):
			j = int(s[i])
			if j % 2 != 0:
				c = i
				break
		if c == -1:
			return ''
		else:
			return s[:c + 1]


class Solution:

	def maxOdd(self, s):
		idx = 0
		result = 0
		for i in range(len(s) - 1, -1, -1):
			if int(s[i]) % 2 != 0:
				return s[:i + 1]
		return ''