(you are here)

Palindrome

Let's solve Palindrome.

Manipulating Strings (Python)

So far in the starter problems, we've only dealt with numerical variables. This is the first problem where we'll need to handle textual data, called strings.

Strings are denoted by single quotes or double quotes (" or '). For example:

  • "Hello World!": You've probably written a program involving this string at some point!
  • "23": This is a string made of two characters: a "2" and a "3". Be careful! The string "23" is not the same as the numerical value 23. 23 + 1 is 24, whereas "23" + 1 will give you an error.
  • "First line\nSecond line" is a string. If you print this string, you'll notice the character \n is not printed literally, it represents a new line, printing the string across two lines.

The individual characters in a string can be accessed like you can access elements of a list:

my_string = "Wow!"
print(my_string[1])
for ch in my_string:
    print(ch)

The code above prints:

  o
  W
  o
  w
  !
  

Strings in Python are immutable. That means you can't modify a string once it is created. If you want to modify an existing string, you first have to turn it into a list. Once you're done modifying it, you have to turn it back into a string:

a = "Wow!"
# a[0] = "B" would be an error, since strings are immutable
a = list(a)
# Now it's okay, because a is a list, not a string.
a[0] = "B" # The string is now "Bow!"
a[2] = a[1] # The string is now "Boo!"
a = "".join(a)
print(a) # Boo!

Hopefully most of that is straightforward. The one complex line in that snippet is "".join(a). That just means take the list a and turn it into a string by joining them together by putting "" (i.e. nothing) between them. " ".join(a) would for example create the string "W o w !". Although not relevant to this problem, join works with lists of numbers too (or lists of anything that Python can work out how to turn into a string).

I haven't discussed how to read strings from files or how to write them, but I'll let the code speak for itself.

# Template for Palindrome
inputFile = open("palin.txt", "r")
outputFile = open("palout.txt", "w")

# Read in the input
N = int(inputFile.readline())
# "readline" also includes the newline marking the end of the line (if there is one).
# We add a .strip() which gets rid of it for us.
line = inputFile.readline().strip()

# Convert the string to a list so we can modify it
line = list(line)

# The characters of the palindrome are line[0], line[1], ..., line[N-1]
# TODO: Solve the problem

# Convert back to a string for printing
line = "".join(line)

outputFile.write(line)

inputFile.close()
outputFile.close()

Manipulating Strings (C++)

So far in the starter problems, we've only dealt with numerical variables. This is the first problem where we'll need to handle textual data, called strings.

A string is just an array of individual characters (like 'a', '7', '\n' or ' '). Characters in C++ are denoted by single quotes (') and have type char.

Strings on the otherhand are denoted by double quotes ("). For example:

  • "Hello World!": You've probably written a program involving this string at some point!
  • "23": This is a string made of two characters: a "2" and a "3". Be careful! The string "23" is not the same as the numerical value 23. 23 + 1 is 24, whereas "23" + 1 will give you an error.
  • "First line\nSecond line" is a string. If you print this string, you'll notice the character \n is not printed literally, it represents a new line, printing the string across two lines.
  • "x" is a string consisting of a single character. Be careful! The string "x" is different from the character 'x'.

Declaring a string in C++ looks like this:

char my_string[] = "Wow!";

This should look familiar to you (remember Dictionary?), the only difference is that we didn't need to give a number between the [ and ] (that's because C++ is smart enough to guess how long the array is supposed to be, but I digress).

The individual characters in a string can be accessed and modified like you can with any array:

char a[] = "Wow!";
a[0] = 'B'; // The string is now "Bow!"
a[2] = a[1]; // The string is now "Boo!"
printf("%s\n", a); // Prints Boo!

Hopefully most of that is straightforward. The one new thing is the %s. You should be used to using %d to print integers, %s is what we use to print strings.

You might have guessed that reading strings is also done with %s. You're right! But there are some differences to reading integers:

// Template for Palindrome
#include<cstdio>

// We don't know in advance how many characters will be in the input
// file, nor can C++ determine it automatically for us.
//
// That's why we make the array big enough to contain the
// largest possible input. Actually, we need to make it one bigger
// than the largest possible input. I won't explain here, but you
// can take a look at https://www.learncpp.com/cpp-tutorial/c-style-strings/
// if you're curious.
char line[100001];
int N;
int main() {
    FILE* inputFile = fopen("palin.txt", "r");
    FILE* outputFile = fopen("palout.txt", "w");

    // Read the input.
    // Notice that unlike with reading integers, we don't have an
    // ampersand (&) before "line".
    //
    // Notice that although N and the string are on different lines,
    // we still only separate them by a space in the format string ("%d %s").
    // This is because a space in the format string actually means "any number
    // of whitespace characters" (which includes spaces, tabs and newlines).
    fscanf(inputFile, "%d %s", &N, line);
    
    for(int i = 0; i < N; i++) {
        // TODO: Replace this with a proper solution
        line[i] = '?';
    }

    fprintf(outputFile, "%s\n", line);

    fclose(inputFile);
    fclose(outputFile);
}

I won't go into detail on how to solve Palindrome. That's for you to work out. Give it a go!

Your turn!


Solve Palindrome to complete this tutorial.