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
- Step 1: Start.
- Step 2: Set isPalindrome = 1.
- Step 3: Read word.
- Step 4: Set i = 0, j = strlen(word) - 1.
- Step 5: If i < j, go to step 6; otherwise go to step 9.
- Step 6: If word[i] != word[j], go to step 7; otherwise go to step 8.
- Step 7: Set isPalindrome = 0. Go to step 9.
- Step 8: Set i++, j--. Go to step 5.
- Step 9: If isPalindrome == 1, go to step 10; otherwise go to step 11.
- Step 10: Print word is a palindrome. Go to step 12.
- Step 11: Print word is not a palindrome.
- 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)
| Step | Line | Box | isPalindrome | word | i | j | Output |
|---|---|---|---|---|---|---|---|
| 1 | 4 | Start | |||||
| 2 | 6 | isPalindrome = 1 | 1 | ||||
| 3 | 9 | Read word | 1 | level | Enter a word: | ||
| 4 | 12 | i = 0, j = strlen(word) - 1 | 1 | level | 0 | 4 | |
| 5 | 13 | i < j? | 1 | level | 0 | 4 | |
| 6 | 14 | word[i] != word[j]? | 1 | level | 0 | 4 | |
| 7 | 19 | i++, j-- | 1 | level | 1 | 3 | |
| 8 | 13 | i < j? | 1 | level | 1 | 3 | |
| 9 | 14 | word[i] != word[j]? | 1 | level | 1 | 3 | |
| 10 | 19 | i++, j-- | 1 | level | 2 | 2 | |
| 11 | 13 | i < j? | 1 | level | 2 | 2 | |
| 12 | 22 | isPalindrome == 1? | 1 | level | 2 | 2 | |
| 13 | 23 | Print word is a palindrome | 1 | level | 2 | 2 | level is a palindrome |
| 14 | 27 | Stop | 1 | level | 2 | 2 |
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.