 # NOPAL - Editorial

Author: Jeevan Jyot Singh
Tester : Takuki Kurokawa
Editorialist: Aman Dwivedi

Simple

Palindromes

# PROBLEM:

You need to construct the string of length N such that none of its substring of length \ge2 is a palindrome.

# EXPLANATION:

Take any string of length 3 such that all the characters of this string are distinct. Now, just keep on repeating this string until you get the desired length N to get the desired string which is asked in the problem.

Why does this work?

Let’s say we have a string X of length 3 such that all the characters are distinct. That means:

X \neq X \\ X \neq X \\ X \neq X

Hence when we repeat this string we get:

X,X,X,X,X,X,.......
• Observe that for any character, the character next to it and before to it is always different.

Now suppose we have generated the string of length N by repeating the string X. Now let’s consider any substring of length \ge2. Let’s say S[i, M] is the substring:

Now to be a palindromic substring the first and last character of this substring should be equal, let’s say :

• S[i] = S[M]

• Now can the characters S[i+1] and S[M-1] be the same ever. The answer is to this is NO as S[i] = S[M] and the characters next to it and before to it are always different.

Hence we can see there won’t be any palindromic substrings of length \ge2 in such construction.

# TIME COMPLEXITY:

O(N) per test case

# SOLUTIONS:

Author's Solution
Tester's Solution
``````#include <bits/stdc++.h>
using namespace std;

int main() {
int tt;
cin >> tt;
while (tt--) {
int n;
cin >> n;
string t = "tabr";
for (int i = 0; i < n; i++) {
cout << t[i % 4];
}
cout << '\n';
}
return 0;
}
``````
Editorialist Solution
``````#include<bits/stdc++.h>
using namespace std;

void solve()
{
int n;
cin>>n;

string s="abc";

for(int i=0;i<n;i++)
cout<<s[i%3];

cout<<"\n";
}

int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);

int t;
cin>>t;

while(t--)
solve();

return 0;
}

``````
1 Like

Why can’t we use "abcdef… .?

You can !!

can’t we use string of length 4 ?

What’s wrong with my code?

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

int main() {
int t;
cin>>t;
while(t--){
int n;
cin>>n;
char arr;
for(int i=0; i<26; i++){
arr[i] = 'a'+i;
}
string s="";
int i=n;
while(n--){
s=s+arr[i-1];
i--;
}
cout<<s<<endl;
//cout<<endl;
}
return 0;
}

``````

When n is say 100, your arr[i-1] will be out of bounds.

why my solution is wrong?

/* package codechef; // don’t place package name! */

import java.util.;
import java.lang.
;
import java.io.*;

class Codechef
{
final private int BUFFER_SIZE = 1 << 16;
private DataInputStream din;
private byte[] buffer;

``````    public Reader()
{
din = new DataInputStream(System.in);
buffer = new byte[BUFFER_SIZE];
}

{
din = new DataInputStream(
new FileInputStream(file_name));
buffer = new byte[BUFFER_SIZE];
}

{
byte[] buf = new byte; // line length
int cnt = 0, c;
while ((c = read()) != -1) {
if (c == '\n') {
if (cnt != 0) {
break;
}
else {
continue;
}
}
buf[cnt++] = (byte)c;
}
return new String(buf, 0, cnt);
}

public int nextInt() throws IOException
{
int ret = 0;
while (c <= ' ') {
}
boolean neg = (c == '-');
if (neg)
do {
ret = ret * 10 + c - '0';
} while ((c = read()) >= '0' && c <= '9');

if (neg)
return -ret;
return ret;
}

public long nextLong() throws IOException
{
long ret = 0;
while (c <= ' ')
boolean neg = (c == '-');
if (neg)
do {
ret = ret * 10 + c - '0';
} while ((c = read()) >= '0' && c <= '9');
if (neg)
return -ret;
return ret;
}

public double nextDouble() throws IOException
{
double ret = 0, div = 1;
while (c <= ' ')
boolean neg = (c == '-');
if (neg)

do {
ret = ret * 10 + c - '0';
} while ((c = read()) >= '0' && c <= '9');

if (c == '.') {
while ((c = read()) >= '0' && c <= '9') {
ret += (c - '0') / (div *= 10);
}
}

if (neg)
return -ret;
return ret;
}

private void fillBuffer() throws IOException
{
BUFFER_SIZE);
buffer = -1;
}

{
fillBuffer();
return buffer[bufferPointer++];
}

public void close() throws IOException
{
if (din == null)
return;
din.close();
}
}
public static void main (String[] args) throws java.lang.Exception
{
//	Scanner sc = new Scanner(System.in);
long T = sc.nextLong();
while(T-->0)
{
long n = sc.nextLong();
// for(int i=97;i<(97+n);i++)
// {
//    System.out.print((char)(i+1));
// }

// System.out.println();
// create a string of all characters
String alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";

// create random string builder
StringBuilder sb = new StringBuilder();

// create an object of Random class
Random random = new Random();

// specify length of random string
for(int i = 0; i < n; i++) {

// generate random index number
int index = random.nextInt(alphabet.length());

// get character specified by index
// from the string
char randomChar = alphabet.charAt(index);

// append the character to string builder
sb.append(randomChar);
}

String randomString = sb.toString();
String original = randomString;
String reverse = " ";
int length = original.length();
for ( int i = length - 1; i >= 0; i-- )
reverse = reverse + original.charAt(i);
if (!(original.equals(reverse)) )
System.out.println(randomString);
}
sc.close();
}
``````

}

Why my code is wrong

#include
using namespace std;
int main()
{
int t;
cin>>t;
while(t–)
{
int N;
cin>>N;
if(N<=26)
{
for(int i=0; i<N; i++)
{
char c=‘a’+i;
cout<<c;
}
}
else {
int p =N%26;
int k=(N-p)/26;
for(int i=0; i<k; i++)
{
for(int i=0; i<26; i++)
{
char c=‘a’+i;
cout<<c;
}
for(int i=0; i<p; i++)
{
char c=‘a’+i;
cout<<c;
}

}
}
cout<<endl;
}
return 0;
}

Accepted approach

``````import java.util.*;
class Main {
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while(t-->0){
String s = "abcdefghijklmnopqrstuvwxyz";
int n = sc.nextInt();
String ans = "";
if(n<=26)
System.out.println(s.substring(0,n));
else{
while(n>0){
if(n>26){
ans+=s.substring(0,26);
n-=26;
}
else{
ans+=s.substring(0,n);
break;
}
}
System.out.println(ans);
}
}
}
}
``````

The main mistake in the code is that for n>26. The logic is correct but the error is in implementation.
According to the logic, if n is divisible by 26, the characters a to z must be printed exactly k times and if n is not divisible by 26, in addition to printing characters k times, the remaining p characters (the first p characters from ‘a’ to ‘z’) must be printed.
So the error is “including the second loop printing p characters in the the loop executing k times.” If you just bring the loop running p times out, the answer be correct Also, you may further shorten the code by removing the if and else checks, as you are calculating k and p, you can simply run the loop as mentioned above, the only thing to change is to make i=1 and i<=k in the first loop and i=1 , i<=p and c=‘a’ + i - 1in the second loop.
For reference for shortening the code , you may check this submission. It is based on your code only, I had just deleted some part and make the changes which are mentioned in the paragraph above. Hope that helps https://www.codechef.com/viewsolution/57023079

1 Like

you have defined your array for 27 elements, but for larger values of i, arr will be out of bounds

That’s literally what I did, I’m attaching my code for reference

#include <bits/stdc++.h>

using namespace std;

void notapalindrome(int n){
string s1=“abcdefghijklmnopqrstuvwxyz”;
string s="";
int i=0;
while(n–){
s=s+s1[i];
if(i==25){
i=0;
}
i++;
}
std::cout << s << std::endl;
}

int main() {
int t;
cin >> t;
while (t–) {
int n;
cin >> n;
notapalindrome(n);
}
return 0;
}

I did my code this way

#include <bits/stdc++.h>
using namespace std;

int main() {
string g=“abcdefghijklmnopqrstuvwxyz”;
int t;
cin>>t;
while(t–){
int n,j;
cin>>n;
if(n>26){
int l=n/26;
for(int i=1;i<=l;i++){
cout<<g;
}
}
string s;
char a=‘a’;
j=((int)a)+(n%26);
int k=0;
for(int i=(int)a;i<j;i++){
s[k]=(char)i;
cout<<s[k];
k++;
}
cout<<endl;
}
return 0;
}