<p>Given a string <code>s</code> containing only digits, return the <span data-keyword="lexicographically-smaller-string">lexicographically smallest string</span> that can be obtained after swapping <strong>adjacent</strong> digits in <code>s</code> with the same <strong>parity</strong> at most <strong>once</strong>.</p>

<p>Digits have the same parity if both are odd or both are even. For example, 5 and 9, as well as 2 and 4, have the same parity, while 6 and 9 do not.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">s = &quot;45320&quot;</span></p>

<p><strong>Output:</strong> <span class="example-io">&quot;43520&quot;</span></p>

<p><strong>Explanation: </strong></p>

<p><code>s[1] == &#39;5&#39;</code> and <code>s[2] == &#39;3&#39;</code> both have the same parity, and swapping them results in the lexicographically smallest string.</p>
</div>

<p><strong class="example">Example 2:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">s = &quot;001&quot;</span></p>

<p><strong>Output:</strong> <span class="example-io">&quot;001&quot;</span></p>

<p><strong>Explanation:</strong></p>

<p>There is no need to perform a swap because <code>s</code> is already the lexicographically smallest.</p>
</div>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>2 &lt;= s.length &lt;= 100</code></li>
	<li><code>s</code> consists only of digits.</li>
</ul>

class Solution:
    def getSmallestString(self, s: str) -> str:
        s_with_sentinel = s + '9'
        lex_smallest = []
        current_index = 0
        end_index = len(s) - 1 # Only need to compare pairs left and right, so the last value need not be checked
        swapped_once = False

        while len(lex_smallest) < len(s):
            left = s_with_sentinel[current_index]
            right = s_with_sentinel[current_index + 1]
            if not swapped_once and self.isSameParity(left, right) and self.shouldSwap(left, right):
                current_index += 2
                lex_smallest.append(right)
                lex_smallest.append(left)
                swapped_once = True
                continue
            lex_smallest.append(left)
            current_index += 1

        return ''.join(lex_smallest)


    def shouldSwap(self, left: str, right: str) -> bool:
        # print(f'Compare: right {right} < left{left}? = {right < left}')
        return right < left

    def isSameParity(self, first: str, second: str) -> bool:
        first_val = int(first)
        second_val = int(second)
        first_parity = first_val % 2
        second_parity = second_val % 2
        return first_parity == second_parity
30