Demo: Palindrome Substrings

Let's take a look at this "Palindrome Substrings" problem using the PEDAC approach.

// Given a string, write a function, `palindromeSubstrings`, that returns
// all the substrings from the given string that are palindromes and have
// a minimum length of two.

// Test cases:

console.log(palindromeSubstrings("supercalifragilisticexpialidocious"));
// should return: ["ili"]

console.log(palindromeSubstrings("abcDDcbA"));
// should return: ["bcDDcb", "cDDc", "DD"]

console.log(palindromeSubstrings("palindrome"));
// should log: []

console.log(palindromeSubstrings(""));
// should log: []

Understand the Problem

Understanding the problem has three steps.

1. Read the problem description.
2. Check the test cases, if any.
3. If any part of the problem is unclear, ask the interviewer or the person prompting you to clarify the matter.

After reading this problem description, some items may need clarification:

1. What is a palindrome? You might ask the interviewer to tell you what a palindrome is, and the interviewer would tell you that it is a word that reads the same forwards and backward.

2. What is a substring? You might ask the interviewer to tell you what a substring is, and the interviewer would tell you that it's a contiguous sequence of characters within a string. For example, in a string "halo", some substrings are "ha", "alo", "lo" etc.

3. Should the characters in the string remain the same if they already use uppercase? Here, you can check the test cases. In the second test case, the input contains the substring "DD" which remains in uppercase in the expected return value.

4. How should I deal with empty strings provided as input? The test cases frequently answer this question. Here, test case number 3 provides the answer. This is an implicit requirement that we can infer from the test cases. Given an empty string as input, we should return an empty array.

5. Can I assume that all inputs are strings? Our test cases don't show any non-string inputs, so you should ask whether the inputs can contain non-string values, and what you should do with these edge cases if so. In this problem, we can expect our argument to always be a string.

6. Should I consider letter case when deciding whether a word is a palindrome? Our second test case showed us that we should maintain the case of a given string, but should the case determine if a substring is a palindrome. Again, our second test case gives us a hint. Our expected output doesn't include the substring "abcDDcbA" but it does include "bcDDcb". It looks like the difference in case between our start "a" and end "A" means that this isn't a palindrome. We could also ask the interviewer if we didn't notice this implicit rule.

7. Always verify your assumptions either by looking at the test cases or by asking the interviewer. Some assumptions, like whether we should treat strings as case-sensitive or not, can be verified either by looking at the problem description, if that is mentioned there, or by checking the test cases. If you can't determine the answer with the test cases or problem description, you should ask the interviewer to clarify this for you.

We should note that this isn't an exhaustive list of questions. These questions apply to this challenge, but the types of questions you ask will vary greatly depending on the problem given. For example, if we were working with an array instead of a string, or rather, a mutable input instead of an immutable one, we should consider whether we can or should mutate our input. Knowing what questions you need answers to in order to solve a problem is an important part of the PEDAC process, and it's something that you will develop an intuition for with time and experience.

To conclude this part of the PEDAC process, you should make sure that you've written down all of the information you've acquired. The problem description should give you your input, output, and a list of explicit rules. Your exploration of the test cases and your own questions should give you a list of implicit rules:

Problem:

• Input: string
• Output: array of substrings
• Rules:
  • Explicit requirements:
    • A palindrome is a word that reads the same forwards and backward.
    • Palindromes must be at least two characters in length. ('a' is not a palindrome, but 'aa' is.)
  • Implicit requirements:
    • Every palindrome in the string must maintain it's case in the returned array.
    • Palindromes are case sensitive ("Dad" is not a palindrome, but "dad" is)
    • If the input is an empty string, the result should be an empty array.

Data Structure / Algorithm

Data structures influence your algorithm, and for that reason, these two steps are often paired. At this stage, deciding what data structure to use often feels intuitive to students, like when choosing between an array and a hash. Designing the right algorithm, on the other hand, is far more challenging. The biggest problem that students have when writing algorithms is providing sufficient detail.

What data structure could we use to solve this problem? The obvious choice seems to be an array since that's the desired output.

Now, we come to the algorithm part. Look at the algorithm written below.

---

• Declare a result variable and initialize it to an empty array
• Create an array named substrArray that will contain all of the substrings of the input string that are at least 2 characters long.
• Loop through the words in the substrArray array.
  • If the word is a palindrome, append it to the result array
• Return the result array

---

Does this algorithm look complete to you?

This algorithm is a "high-level" algorithm and it resembles those that we often see students write during interviews. It looks complete, but let's think about it for a moment: What is the hardest part of this problem? Is it looping through an array and pushing substrings that are palindromes in the result array? Is it determining whether a substring is a palindrome? Is it something else entirely?

Determining whether a word is a palindrome isn't that difficult for most students. Looping through the array and selecting all the palindromes is relatively easy as well. However, finding all the substrings for a given string can be challenging. The above algorithm doesn't tackle that issue. It lacks implementation details for the "hard" parts.

When a student starts writing code based on this algorithm, they soon realize that returning all the substrings won't be easy. Ideally, the student should return to the algorithm and try to come up with a way to find all the substrings from the input string. They might even create a new method named substrings that returns the array of substrings. In practice, though, the time limitations often lead them to take a hack & slash approach instead. That almost always leads to spending more time than necessary on the problem or, worse yet, not solving it at all.

Let's now follow the correct approach. The student can use the "high-level" algorithm from above and first write the code for it. The code might look like this:

function palindromeSubstrings(str) {
  let result = [];
  let substringsArr = substrings(str);

  substringsArr.forEach(substring => {
    if (isPalindrome(substring)) {
      result.push(substring);
    }
  });

  return result;
}

Note that we are calling functions named substrings and isPalindrome. We haven't defined those functions yet. Instead of trying to write the code for these subproblems on the fly, let's return to our algorithm and flesh out their logic. To start, let's investigate our substrings helper function.

To find a working algorithm, we can simplify the problem by using a small, concrete example to determine what we need to do. For instance, we can start with a short word like "halo" and write all its substrings that are at least 2 characters in length. The resulting list is ["ha", "hal", "halo", "al", "alo", "lo"]. Do you see a pattern here? It's clear that some sort of complex looping is going on.

The first loop - the outermost loop - iterates over the starting index for the substrings. With "halo" as a starting string, we need to iterate over the letters "h", "a", and "l". (We don't need to iterate over "o" since there are no substrings of at least 2 characters that start with "o".)

Within the first loop, we'll iterate over the possible ending indices of our substrings. The ending index needs to start at least two positions after the starting index. This is because JavaScript's slice method excludes the character at the provided ending index.

Consider the string "halo". Calling "halo".slice(0, 2) returns "ha". Notice that the character at index 2 ("l") is not included in the result.

Here's that looping pattern written out in an algorithm:

---

• for each starting index from 0 through the next to last index position
  • for each ending index from 2 until the length of the string
    • extract the substring between the starting index up to but not including the ending index
  • end of inner loop
• end of outer loop

---

The First Outer Loop Iteration

Beginning with the first letter of the string at index 0, 'h', we first find all of the substrings that begin with that letter: ['ha', 'hal', 'halo']. As you can see, we're showing the inner loop at work here:

• First, we get a 2-letter substring that begins at index 0 and ends at index 2: 'ha'

• Next, we get a 3-letter substring that begins at index 0 and ends at index 3: 'hal'

• Finally, we get a 4-letter substring that begins at index 0 and ends at index 4: 'halo'

The loop, in this case, is one that starts with an index 2 and ends with an index of 4.

---

The Second Outer Loop Iteration

Next, we need to find the substrings that start at index 1 (a). The loop, in this case, starts with an index of 3 and ends with an index of 4.

• First, we get a 2-letter substring that begins at index 1 and ends at index 3: 'al'

• Next, we get a 3-letter substring that begins at index 1 and ends at index 4: 'alo'

---

The Third Outer Loop Iteration

Finally, we get all of the substrings that begin at index 2. This time, the loop starts and ends with an index of 4, so there is only one iteration:

• We get a 2-letter substring that begins at index 2 and ends at index 4: 'lo'

---

What would happen if the original string was, say, 7 characters in length, such as goalies? In that case, we'd still have to go through the same process - an outer loop that iterates from index 0 (the letter g) to index 5 (the letter e), and an inner loop that starts with index startIdx + 2 and continues until 7:

• On the first iteration of the outer loop, the ending index used in the inner loop ranges from 2 to 7.
• On the second iteration, the ending index ranges from 3 to 7.
• On the third iteration, the ending index ranges from 4 to 7.
• On the fourth iteration, the ending index ranges from 5 to 7.
• On the fifth iteration, the ending index ranges from 6 to 7.
• On the sixth, the ending index starts and ends at 7.

Looking at these two examples, we can determine that the outer loop iterates over indices from 0 to the length of the next to the last index position (i.e., string.length - 2). We can also see that the inner loop ranges from the starting index plus two (startIdx + 2) to the original string length. We can use both of these facts in our algorithm. Let's go ahead and write the complete algorithm for this function:

---

substrings Algorithm

• Create an empty array called result that will contain all required substrings
• Create a startIdx variable (value 0) for the starting index of a substring
• Start a loop that uses startIdx to iterate over string from 0 to the length of the string minus 2
  • Create an endIdx variable (value startIdx + 2) for the ending index of a substring
  • Start an inner loop that uses endIdx to iterate over string from startIdx + 2 to string.length
    • Extract a substring between the startIdx and endIdx
    • Append the extracted substring to the result array
    • Increment the endIdx variable by 1
  • End the inner loop
  • Increment the startIdx variable by 1
• End the outer loop
• Return the result array

---

Here's some code that we might write for the substrings function:

function substrings(str) {
  let result = [];
  let startIdx = 0;

  while (startIdx <= str.length - 2) {
    let endIdx = startIdx + 2;
    while (endIdx <= str.length) {
      let substring = str.slice(startIdx, endIdx);
      result.push(substring);
      endIdx += 1;
    }

    startIdx += 1;
  }

  return result;
}

Checking whether the string is a palindrome is easy enough. However, we can write a function for it to help make our code more readable. Let's include that function in our algorithm.

• Inside the isPalindrome function, check whether the string value is equal to its reversed value

You can use the Array.prototype.reverse method along with split and join:

function isPalindrome(str) {
  return str === str.split('').reverse().join('');
}

Complete PEDAC

We've finished all of the steps necessary to create a complete PEDAC:

Problem:

• Input: string
• Output: array of substrings
• Rules:
  • Explicit requirements:
    • A palindrome is a word that reads the same forwards and backward.
    • Palindromes must be at least two characters in length. ('a' is not a palindrome, but 'aa' is.)
  • Implicit requirements:
    • Every palindrome in the string must maintain it's case in the returned array.
    • Palindromes are case sensitive ("Dad" is not a palindrome, but "dad" is)
    • If the input is an empty string, the result should be an empty array.

Algorithm:

substrings function

• Create an empty array called result that will contain all required substrings
• Create a startIdx variable (value 0) for the starting index of a substring
• Start a loop that uses startIdx to iterate over string from 0 to the length of the string minus 2
  • Create an endIdx variable (value startIdx + 2) for the ending index of a substring
  • Start an inner loop that uses endIdx to iterate over string from startIdx + 2 to string.length
    • Extract a substring between the startIdx and endIdx
    • Append the extracted substring to the result array
    • Increment the endIdx variable by 1
  • End the inner loop
  • Increment the startIdx variable by 1
• End the outer loop
• Return the result array

isPalindrome function

• Inside the isPalindrome function, check whether the string value is equal to its reversed value

palindromeSubstrings function

• Declare a result variable and initialize it to an empty array
• Create an array named substrArray that will contain all of the substrings of the input string that are at least 2 characters long.
• Loop through the words in the substrArray array.
  • If the word is a palindrome, append it to the result array
• Return the result array

Solution Code

The code for our main problem, palindromeSubstrings, along with all of the helper functions:

function substrings(str) {
  let result = [];
  let startIdx = 0;

  while (startIdx <= str.length - 2) {
    let endIdx = startIdx + 2;
    while (endIdx <= str.length) {
      let substring = str.slice(startIdx, endIdx);
      result.push(substring);
      endIdx += 1;
    }

    startIdx += 1;
  }

  return result;
}

function isPalindrome(str) {
  return str === str.split('').reverse().join('');
}

function palindromeSubstrings(str) {
  let result = [];
  let substringsArr = substrings(str);

  substringsArr.forEach(substring => {
    if (isPalindrome(substring)) {
      result.push(substring);
    }
  });

  return result;
}

console.log(palindromeSubstrings("supercalifragilisticexpialidocious")); // ["ili"]
console.log(palindromeSubstrings("abcddcbA"));   // ["bcddcb", "cddc", "dd"]
console.log(palindromeSubstrings("palindrome")); // []
console.log(palindromeSubstrings(""));           // []

Takeaways

Once again, we want to emphasize that you don't need to write all your pseudocode before you start coding. As you saw above, we first wrote the pseudocode for the palindromeSubstrings function. We then wrote the corresponding JavaScript code before we returned to write the pseudocode for the other two functions. Afterwards, we wrote the corresponding code, and then returned to the two lower-level functions.

Finally, the main takeaway is that you should be able to write a plain English solution to the problem. If you can't do that, you won't be able to code it either. You also don't need any "fancy" functions to solve these problems.

In conclusion, we suggest you practice working through the PEDAC process while solving problems. It may be hard at first, and for simple problems, it might even seem unnecessary, but stick with it. In time, your process will improve, and you'll soon be able to solve difficult problems much more readily.