Python Palindrome Detection, F Strings, Ternary Operators, and Fail Fast Optimizations

The other day I was scrolling through a learning Python Facebook group that I contribute in to help people and ran across a seemingly simple post where someone was asking why he was getting a highlight error in his IDE. The original poster also wanted to know if this was the correct way to write this. The code is as below.

# S1 takes input from a user

s1 = input()

# s1 is stored in variable a in reverse order

# Manually reverse the string
a = ''
    
for char in s1:

    a = char + a

if s1==a:

  print("its a palindrome")

else:

  print("its not a palindrome")

While this code is correct for basic cases of a palindrome such as “bob” it definitely has some room for improvement.

Feedback:

  • Too many blank lines
  • Have spaces around your operators such as ‘if s1 == a’
  • Very inefficient way to reverse a string
  • Input should give a prompt to the user what the program does
  • Using a if else block for a simple logic check isn’t Pythonic
  • Repeated strings which uses heap memory
  • “it’s” instead of “its”, but that is just a grammar thing and the poster probably isn’t a native English speaker which is fine
  • wrong output for “Race car”

Sure for a simple toy application from a beginner this is fine code. But to get in the habit of preparing for a career as a developer it is good to establish good coding practices earlier. This helps you write more maintainable code in the future when you are working harder problems or for your job where the code needs to be maintained for a longer time and may be worked on by multiple developers.

A better approach

s1 = input("Please enter text to test if it's a palindrome\n")

print(f"It's {'' if s1 == s1[::-1] else 'not'} a palindrome")

Ah, much simpler! To achieve this we utilize the splicing notation, F strings which are fast formatted strings, and a ternary operator to simplify our logic check, and reduce line usage to be able to visually process longer code in one screen.

Although this code is cleaner, it still only detects basic palindromes like “bob” and “racecar”. If we input “Race car” it would say it’s not a palindrome even though generally spacing, casing, and special characters are ignored for the sake of cool palindromes. Before we fix for that let’s talk a little more about F Strings and Ternary operators.

F Strings

F strings or “fast formatted strings” are a feature introduced in Python3.6 and later that allow you to create complex strings in a easy to read way. Also the python magic it uses for interpolation can be bench-marked and proven faster than using basic string concatenation or python 2.7’s string formatting. I’ll give examples of this all below.

age = 25
world = "world"
hobby="coding"

# Basic string concatenation
print("Hello " + world)
print("Our age is: " + age) # Error from joining int and str
print("Our age is: " + str(age)) # Ugly code
print("Hello " + world + " , I am " + age + " years old.") 

# Improvement with str interpolation
# This will insert the variable where the '%s' string markers are
# Also does direct string format casting for non-Str types
print("Hello %s" % world)
print("My age is: %s" %  age)

# You can also use this to insert multiple
#
# This works but takes some effort to recognize what variable goes where
print("Hello %s, I am %s years old. I like to %s" % (world, age, hobby))

# Using F strings
#
# The f before the string quote tells the Python interpreter
# to treat this as an F string and auto format it for us.
print(f"Hello {world}, I am {age} years old. I like to {hobby}")

# Formatting inline code
print(f"I am {10 + 15} years old")

def calc_age(val1, val2):
  return val1 + val2
# Running functions
print(f"I am {calc_age(10,15)} years old") 

You can see the f string is much easier to read and follow than the str interpolation and also runs slightly quicker if you need to output a lot of formatted text in your program.

Ternary Operators

A ternary operator is a way to do single line logic checks for simple conditions such as printing output in f strings, initializing a variable, or logic forking.

# F string printing
is_world = True

# Normal way which is a lot of lines for something simple
if is_world:
  print("Hello world")
else:
  print("Hello not the world"

# Simpler ternary usage
print(f"Hello {'world' if is_world else 'not the world'})

# Optional variable initialization
#
# Provide a way for the caller of the function to pass in their own logger
def inject_logger(logger=None):
  obj = logger if logger else logging.getLogger("local logger")

# Logic forking
def greet_coder():
  print("Hello coder!")

def greet_non_coder():
  print("Hello non coder!")

# Assume the person will only ever enter yes or no
can_code = input("Can you code? [y/n]")

greet_coder() if can_code == 'y' else greet_non_coder()

Formatting User Input

Now that we have a deeper understanding of F Strings and Ternary operators my suggested code should make more sense. But as I stated earlier it doesn’t work for “Race car”. When working with user input your code should make assumptions about what the user is inputting and you should format that input to meet the expectations of your code. For example maybe your program expects integers for ‘guess the number’ type programs and the input is a string.

For our palindrome program we should clean the user input to make everything lower case and to remove special characters and spaces.

import re

s1 = input("Please enter text to test if it's a palindrome\n")

# Make everything lower case
#
# o(n)
s1 = s1.lower()

# Remove special characters using a regex
#
# o(n)
s2 = re.sub('[^A-Za-z0-9]+', '', s1)

# Since this is a common operation Python has a special method for it
#
# This is o(n)
s3 = ''.join(e for e in s1 if e.isalnum())

# These should always be true
print(f"S2 and S3 are the same: {s2 == s3}")

# 2 * o(n)
print(f"It's {'' if s3 == s3[::-1] else 'not'} a palindrome")

The code above is now functional for phrases such as “A man, a plan, a canal: Panama”. However you can see there are multiple operations in our algorithm which are O(n) in Big Oh notation which is an important concept in computer science. It is a way to make assumptions about an algorithms efficiency as the number of inputs increases drastically and the program scales.

Big O breakdown of the above algorithm

If you’re familiar with big O notation for estimating complexities please feel free to skip. In the above example our input is a string, and our algorithm is dependent on the number of characters in our string. If our string has 7 letters as in the case of “Racecar”, to reverse our string we need to run a few operations on 7 inputs to move an iterator and concatenate the reversed string, this ends up being noted as O(n) or for every input n we do something n number of times.

To format things to lower case again we do another algorithm on 7 inputs to check if it’s upper case and change it to lower in our string array for an index of our loop.

The above algorithm ends up being 5 o(n) , for “Racecar” input there is roughly 35 set of operations we do. And while 35 is much bigger than an input of 7 it is still a linear increase and from the sake of a computer processor it’s not much different so the overall complexity is o(n).

This becomes more obvious when you look into exponential functions that run in o(n^2) where 7 inputs created 49 operations and 10 inputs generates 100 operations. These are the kind of algorithms that really slow down growing systems. Increasing the multiplier of a o(n^2) algorithm does not have as much impact on the runtime as adding another input (N).

Optimizing the Palindrome problem

What if I told you that you could clean the input and run your comparison all in a single iteration of the input string by using left and right points to divide our steps. Also doing this will dramatically increase the speed of the algorithm on large input strings. Ultimately, it will end up turning this from an O(n) algorithm into an O(log n) algorithm or logarithmic time.

s1 = input("Please enter text to test if it's a palindrome\n")

# Create left and right pointers
l = 0
r = len(s1) - 1

# Initialize our palindrome flag
is_palindrome = True

while l <= r:
    # Move left pointer if we see a non alphanumeric symbol
    if not s1[l].isalnum():
        l += 1
        continue
    # Move right pointer if we see a non alphanumeric symbol
    if not s1[r].isalnum():
        r -= 1
        continue
    # Break early condition
    if s1[r].lower() != s1[l].lower():
        is_palindrome = False
        break
    l += 1
    r -= 1

print(f"It's {'' if is_palindrome else 'not'} a palindrome")

Benchmarking slow palindrome verse optimized palindrome

To analyze the above optimizations I wrote this code:

# Standard imports
import time

# Local imports
from optimized_palindrome import optomized
# Code from Formatting User Input section
# using the manual iteration for reversing and not [::-1]
# the splicing notation
from format_input import format_and_test_palindrome

test_palindrome = "aaAa&a aAa$$aa*aAa" * 10000

lots_of_tests = [test_palindrome] * 5

start = time.time()
for test in lots_of_tests:
   format_and_test_palindrome(test)
end = time.time()
print(f"Slow palindrome latency: {end-start} sec")

start = time.time()
for test in lots_of_tests:    
    optomized(test)
end = time.time()
print(f"Optimized palindrome latency: {end-start} ms")

"""
Slow palindrome latency: 1.0955910682678223 sec
Optimized palindrome latency: 0.17553067207336426 ms
"""

"""
Output when using [::-1] for reversing.

Python appears to be doing some magic memory manipulation using this
that is more optimal than the two pointer iteration

Slow palindrome latency: 0.046877145767211914 sec
Optimized palindrome latency: 0.22790813446044922 ms
"""

# 2nd test
# Use input that is not a palindrome on 10x longer input string
test_palindrome = "aBaAa&a aAa$$aa*aAa" * 1000000

"""
Benchmark result

Slow palindrome latency: 0.5924203395843506 sec
Optimized palindrome latency: 0.0069828033447265625 ms
"""

As you can see in the benchmark output reversing your own string is extremely less efficient than using [::-1]. The main optimization in our two pointer algorithm is the ability to break the loop early when we see two different characters in our palindrome check. This demonstrates the efficiency of writing your business logic in a way you can fail fast and do operations in your input in a way to do them as needed and verify as soon as possible.

About Stefan Bradstreet

Stefan is a software development engineer II at Amazon with 5+ years of experience in tech. He is passionate about helping people become better coders and climbing the ranks in their careers as well as his own through continued learning of leadership techniques and software best practices.


One thought on “Python Palindrome Detection, F Strings, Ternary Operators, and Fail Fast Optimizations

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s