Given an even integer N, the task is to construct a string such that the total number of distinct substrings of that string that are not a palindrome equals N2.
Examples:
Input: N = 2
Output: aabb
Explanation:
All the distinct non-palindromic substrings are ab, abb, aab and aabb.
Therefore, the count of non-palindromic substrings is 4 = 2 2
Input: N = 4
Output: cccczzzz
Explanation:
All distinct non-palindromic substrings of the string are cz, czz, czzz, czzzz, ccz, cczz, cczzz, cczzzz, cccz, ccczz, ccczzz, ccczzzz, ccccz, cccczz, cccczzz, cccczzzz.
The count of non-palindromic substrings is 16.
Approach:
It can be observed that, if the first N characters of a string are the same, followed by N identical characters different from the first N characters, then the count of distinct non-palindromic substrings will be N2.
Proof:
N = 3
str = “aaabbb”
The string can be split into two substrings of N characters each: “aaa” and “bbb”
The first character ‘a’ from the first substring forms N distinct non-palindromic substrings “ab”, “abb”, “abbb” with the second substring.
Similarly, first two characters “aa” forms N distinct non-palindromic substrings “aab”, “aabb”, “aabbb”.
Similarly, remaining N – 2 characters of the first substring each form N distinct non-palindromic substrings as well.
Therefore, the total number of distinct non-palindromic substrings is equal to N2.
Therefore, to solve the problem, print ‘a’ as the first N characters of the string and ‘b’ as the next N characters of the string.
Below is the implementation of the above approach:
C++
// C++ Program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Function to construct a string// having N*N non-palindromic substringsvoid createString(int N){ for (int i = 0; i < N; i++) { cout << 'a'; } for (int i = 0; i < N; i++) { cout << 'b'; }}// Driver Codeint main(){ int N = 4; createString(N); return 0;} |
Java
// Java Program to implement// the above approachclass GFG{// Function to construct a string// having N*N non-palindromic substringsstatic void createString(int N){ for (int i = 0; i < N; i++) { System.out.print('a'); } for (int i = 0; i < N; i++) { System.out.print('b'); }}// Driver Codepublic static void main(String[] args){ int N = 4; createString(N);}}// This code is contributed by shivanisinghss2110 |
Python3
# Python3 program to implement# the above approach# Function to construct a string# having N*N non-palindromic substrings def createString(N): for i in range(N): print('a', end = '') for i in range(N): print('b', end = '')# Driver CodeN = 4createString(N)# This code is contributed by Shivam Singh |
C#
// C# program to implement// the above approachusing System;class GFG{// Function to construct a string// having N*N non-palindromic substringsstatic void createString(int N){ for(int i = 0; i < N; i++) { Console.Write('a'); } for(int i = 0; i < N; i++) { Console.Write('b'); }}// Driver Codepublic static void Main(String[] args){ int N = 4; createString(N);}}// This code is contributed by Princi Singh |
Javascript
<script>// JavaScript program for the above approach// Function to construct a string// having N*N non-palindromic substringsfunction createString(N){ for (let i = 0; i < N; i++) { document.write('a'); } for (let i = 0; i < N; i++) { document.write('b'); }} // Driver Code let N = 4; createString(N); </script> |
aaaabbbb
Time Complexity: O(N)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!