# Problem Statement
Given a string find all non-single letter substrings that are palindromes. For instance:

<br>

# Hint
* Find substrings

<br>

# Try it yourself

int find_all_palindrome_substrings(string & input) {
  //TODO: Write - Your - Code
  return -1;
}

# include <iostream>
# include <string>
using namespace std;

class PalindromeSubStrings{
  public static int findAllPalindromeSubstrings(String input) {
      //TODO: Write - Your - Code
      return -1;
  }
}

Java

def find_all_palindrome_substrings(input):
  # TODO: Write - Your - Code
  return -1

Python

let findAllPalindromeSubstrings = function(input) {
  //TODO: Write - Your - Code
  return -1;
};

JavaScript

def find_all_palindrome_substrings(input)
  #TODO: Write - Your - Code
  return -1
end

Ruby

int find_palindromes_in_sub_string(const string& input, int j, int k) {
  int count = 0;
  for (; j >= 0 && k < input.length(); --j, ++k) {
    if (input[j] != input[k]) {      
      break;
    } 
    cout << input.substr(j, k - j + 1) << endl;
    ++count;
  }
  return count;
}

int find_all_palindrome_substrings(const string& input) {
  int count = 0;
  for (int i = 0; i < input.length(); ++i) {    
    count += find_palindromes_in_sub_string(input, i - 1, i + 1);
    count += find_palindromes_in_sub_string(input, i, i + 1);
  }
  return count;
}

int main() {
  string str = "aabbbaa";

  cout << "Total palindrome substrings: "  << find_all_palindrome_substrings(str) << endl;
}

class PalindromeSubStrings{
  public static int findPalindromesInSubString(String input, int j, int k) {
    int count = 0;
    for (; j >= 0 && k < input.length(); --j, ++k) {
      if (input.charAt(j) != input.charAt(k)) {      
        break;
      } 
      System.out.println(input.substring(j, k+1));
      count++;
    }
    return count;
  }

  public static int findAllPalindromeSubstrings(String input) {
    int count = 0;
    for(int i = 0 ; i < input.length() ; ++i) {
      count+= findPalindromesInSubString(input, i-1, i+1);
      count+= findPalindromesInSubString(input, i, i+1);
    }

    return count;
  }

  public static void main(String[] args) {
    String str = "aabbbaa";
    int count = findAllPalindromeSubstrings(str);
    System.out.println("Total palindrome substrings: " + count);
  }
}  

def find_palindromes_in_sub_string(input, j, k):
  count = 0
  while j >= 0 and k < len(input):
    if input[j] != input[k]:
      break
    print(input[j: k + 1])
    count += 1

    j -= 1
    k += 1

  return count


def find_all_palindrome_substrings(input):
  count = 0
  for i in range(0, len(input)):
    count += find_palindromes_in_sub_string(input, i - 1, i + 1)
    count += find_palindromes_in_sub_string(input, i, i + 1)

  return count


s = "aabbbaa";
print("Total palindrome substrings: ", find_all_palindrome_substrings(s))

def find_palindromes_in_sub_string(input, j, k)
  count = 0
  while (j >= 0 && k < input.length)
    if (input[j] != input[k])
      break
    end
    puts (input[j .. k])
    count+=1
    j-=1
    k+=1
  end
  return count
end

def find_all_palindrome_substrings(input)
  count = 0
  for i in 0 .. input.length-1
    count += find_palindromes_in_sub_string(input, i - 1, i + 1)
    count += find_palindromes_in_sub_string(input, i, i + 1)
  end
  return count
end


s = "aabbbaa"
count = find_all_palindrome_substrings(s)
print "Total palindrome substrings: ", count, "\n"

# Solution Explanation
## Runtime complexity
The runtime complexity of this solution is polynomial, $O(n^{2})$

## Memory complexity
The memory complexity of this solution is constant, O(1).

<br>

## Solution Breakdown
For each letter in the input string, start expanding to the left and right while checking for even and odd length palindromes. Move to the next letter if we know a palindrome doesn’t exist.

We expand one character to the left and right and compare them. If both of them are equal, we print out the palindrome substring.

> Practice problems like this and many more by checking out our [Grokking the Coding Interview: Patterns for Coding Questions](https://www.educative.io/courses/grokking-the-coding-interview) course!

Find All Palindrome Substrings

Problem Statement

Hint

Try it yourself

Solution

Solution Explanation

Runtime complexity

Memory complexity

Solution Breakdown