Palindrome String: flowchart, algorithm and program

This program reads a word and checks whether it reads the same forwards and backwards. It puts one index at the first character and another at the last, then compares them while moving both toward the middle.

▶ Watch the dry run step by step →

Algorithm

  1. Step 1: Start.
  2. Step 2: Set isPalindrome = 1.
  3. Step 3: Read word.
  4. Step 4: Set i = 0, j = strlen(word) - 1.
  5. Step 5: If i < j, go to step 6; otherwise go to step 9.
  6. Step 6: If word[i] != word[j], go to step 7; otherwise go to step 8.
  7. Step 7: Set isPalindrome = 0. Go to step 9.
  8. Step 8: Set i++, j--. Go to step 5.
  9. Step 9: If isPalindrome == 1, go to step 10; otherwise go to step 11.
  10. Step 10: Print word is a palindrome. Go to step 12.
  11. Step 11: Print word is not a palindrome.
  12. Step 12: Stop.

Program in C, Python and Java

Palindrome String program in C

#include <stdio.h>
#include <string.h>

int main() {
    char word[100];
    int i, j, isPalindrome = 1;

    printf("Enter a word: ");
    scanf("%s", word);

    i = 0;
    j = strlen(word) - 1;
    while (i < j) {
        if (word[i] != word[j]) {
            isPalindrome = 0;
            break;
        }
        i++;
        j--;
    }

    if (isPalindrome)
        printf("%s is a palindrome\n", word);
    else
        printf("%s is not a palindrome\n", word);

    return 0;
}

Palindrome String program in Python

word = input("Enter a word: ")

i = 0
j = len(word) - 1
is_palindrome = True
while i < j:
    if word[i] != word[j]:
        is_palindrome = False
        break
    i += 1
    j -= 1

if is_palindrome:
    print(word, "is a palindrome")
else:
    print(word, "is not a palindrome")

Palindrome String program in Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.print("Enter a word: ");
        String word = sc.next();

        int i = 0;
        int j = word.length() - 1;
        boolean isPalindrome = true;
        while (i < j) {
            if (word.charAt(i) != word.charAt(j)) {
                isPalindrome = false;
                break;
            }
            i++;
            j--;
        }

        if (isPalindrome)
            System.out.println(word + " is a palindrome");
        else
            System.out.println(word + " is not a palindrome");
    }
}

Sample input: word = level
Output: level is a palindrome

How it works

  • i starts at 0 (first character) and j starts at strlen(word) - 1 (last character). isPalindrome starts as 1, meaning we assume it is a palindrome until proven otherwise.
  • The while (i < j) loop compares word[i] with word[j]. If they differ, isPalindrome becomes 0 and break stops the loop right away.
  • If the characters match, i++ and j-- move both indexes one step inward, and the next pair is compared.
  • The loop ends when i and j meet or cross, so every pair has been checked. For 'level' the pairs are l-l and e-e, and the middle 'v' needs no comparison.
  • After the loop, isPalindrome decides which message is printed: 'is a palindrome' or 'is not a palindrome'.

Dry run (trace table)

StepLineBoxisPalindromewordijOutput
14Start
26isPalindrome = 11
39Read word1levelEnter a word:
412i = 0, j = strlen(word) - 11level04
513i < j?1level04
614word[i] != word[j]?1level04
719i++, j--1level13
813i < j?1level13
914word[i] != word[j]?1level13
1019i++, j--1level22
1113i < j?1level22
1222isPalindrome == 1?1level22
1323Print word is a palindrome1level22level is a palindrome
1427Stop1level22

Time and space complexity

Time: O(n) · Space: O(1). The loop makes at most n/2 character comparisons using only a few extra variables.

Common mistakes

  • Using i <= j or looping over the full length. You only need to check half the word, since comparing every pair again just repeats the work.
  • Forgetting to set isPalindrome = 0 before break, or forgetting to initialise it to 1, so the result is wrong.
  • Writing strlen(word) instead of strlen(word) - 1 for j. That points at the '\0' terminator and the first comparison fails.
  • Using scanf("%s") and expecting it to read phrases with spaces. It stops at the first space, so only single words work. Also, 'Level' is not a palindrome here because 'L' and 'l' differ.

Viva questions

Q1. What is a palindrome, and how does your program check for one?

A palindrome reads the same forwards and backwards, like 'madam'. The program puts i at the first character and j at the last, compares them, and moves both inward until they meet or a mismatch is found.

Q2. Why is isPalindrome initialised to 1?

We assume the word is a palindrome until proven otherwise. Only a mismatch sets it to 0, so if no mismatch occurs, it stays 1 and the word is reported as a palindrome.

Q3. Why is j set to strlen(word) - 1 and not strlen(word)?

Indexes start at 0, so the last character is at position length - 1. Position strlen(word) holds the '\0' terminator, and comparing against it would give wrong results.

Q4. Why does the loop condition use i < j and not i <= j or i < strlen(word)?

Once i and j meet or cross, every pair has already been compared, so the loop can stop. If the length is odd, the middle character is only compared with itself, which is unnecessary. Looping to the full length would just repeat every comparison in reverse.

Q5. What is the purpose of the break statement on line 16?

As soon as one pair of characters differs, the answer is known to be 'not a palindrome'. The break exits the loop immediately instead of checking the remaining characters.

Q6. What happens if the user enters a single character like 'a', or an empty input?

For 'a', j is 0, so i < j is false, the loop never runs and it is reported as a palindrome, which is correct. For empty input, scanf would not store a word, so word is uninitialised and strlen(word) - 1 is undefined, because strlen returns an unsigned value and subtracting 1 from 0 wraps around.

Q7. What is the time complexity of this program, and does it need extra space?

It is O(n), where n is the length of the word, because at most n/2 pairs are compared. It uses O(1) extra space, since it only uses the two index variables and a flag.

Q8. What would change if the program had to accept a phrase like 'nurses run' or ignore upper and lower case?

scanf("%s") stops at the first space, so you would read the whole line with fgets instead. You would also skip non-letter characters and compare using tolower() on both characters, so that 'Madam' counts as a palindrome. The two-pointer logic itself stays the same.

Frequently asked questions

Why does the loop only run while i < j?

Once i and j meet or cross, every pair of mirrored characters has already been compared. The middle character of an odd-length word always matches itself, so it needs no check.

Is this check case-sensitive?

Yes. The code compares characters directly, so 'Level' is reported as not a palindrome because 'L' and 'l' are different. To ignore case, convert both characters with tolower() before comparing.

What is the time complexity of this palindrome check?

It is O(n), where n is the length of the word, since at most n/2 pairs are compared. It uses O(1) extra space because it only needs the indexes i and j and a flag.

More programs

← All programs

Try AI Flowchart free →