What is a subsequence in a string?

A subsequence in a string is a new string formed from the original string by removing some (or none) of the characters without affecting the relative ordering of the remaining characters. (For example, "abb" is a subsequence of "aabbcc," but "acb" is not.)

What is a prime string?

Prime string is a string that is a prime number when converted into its numeric form. A prime number is a number that is divisible only by 1 and the number itself. For example, 2, 3, 5, 7, 11, 13 are all prime numbers.

Find the Length of Smallest Non-Prime Subsequence in a Numeric String

Problem

Given a string S of integers [1, 9]. Print the length of the smallest non-prime subsequence of the string S. Print "-1" if all the subsequences are prime.

A non-prime subsequence is a subsequence such that it is not a prime number. Non-prime numbers are composite numbers that have more than two factors. These numbers can also be divided by other numbers except one and itself.

For example, 27, 24, 74, 274 are the non-prime subsequences of the string 274.

Input: A string S.

Output: Print the length of the smallest non-prime subsequence of the string S

Example,

Input: S = "235"

Output: 2

Explanation:There are seven non-empty subsequences {"2", "3", "5", "23", "25", "35", "235"}. Among these subsequences, four subsequences are not prime, i.e., "23", "25", "35", and "235". Thus the smallest non-prime subsequence of the string S is "25" of length 2.

Input: S = "14"

Output: 1

Explanation: There are three non-empty subsequences {"1", "4", "14"}. Among these subsequences, three subsequences are not prime, i.e., "1", "4", and "14". Thus the smallest non-prime subsequence of the string S is "1" of length 1.

Input: S = "23"

Output: -1

Alert Ninjas: Don’t stop now! Enroll in the Competitive Programming course today. Learn the art of writing time and space-efficient code and compete in code competitions worldwide.

Recommended: Try to solve it yourself before moving on to the solution.

Solution

Algorithm:

The smallest possible length of the non-prime subsequence is 1. The prime numbers with length 1 are 2, 3, 5, 7. Now while iterating over the string S, return 1 if we find a subsequence of length 1 with a non-prime digit.
If S is of length < 2, return -1.
If the answer is not 1, it implies all the digits in the string S are 2, 3, 5, or 7. The prime numbers of length 2 with digits 2, 3, 5, and 7 are 23, 37, 53, and 73. Now iterate over the subsequence of length 2 and check if the subsequence is not one of these: 23, 37, 53, and 73, return 2.
If S is of length < 3, return -1.
There is no prime number with length 3 and digits 2, 3, 5, and 7. Therefore return 3 as an answer.

C++

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

// Function to return the length of the smallest non-prime subsequence.
int smallestLength(string s)
{
// Checking for a subsequence of length 1.
for (int i = 0; i < s.length(); i++)
{
  // If a non-prime subsequence of length 1 is found, return 1.
if (s[i] != '2' && s[i] != '3' && s[i] != '5' && s[i] != '7')
{
return 1;
}
}

if( s.length() == 1)
  return -1;

// Checking for a subsequence of length 2.
  for (int i= 0; i < s.length() - 1; i++)
{
  for (int j = i + 1; j < s.length(); j++)
{
string num = to_string(s[i] + s[j]);

  // If a non prime subsequence of length 2 is found, return 2.
if (num != "23" && num != "37" && num != "53" && num != "73")
{
return 2;
}
}

}

// Return 3 if length of S is >= 3 as no subsequence of length 3 // with digits 2, 3, 5, and 7 is prime.
if( s.length() >= 3)
return 3;

return -1;
}

int main()
{
string S = "235";
cout<<smallestLength(S);
return 0;
}

Input: S = "235".

Output: 2

Time Complexity: O(N²), where N is the length of string S. As O(N) time is taken to check for the subsequence of length 1, and O(N²) time is taken to check for the subsequent length 2.

Space Complexity: O(1).

Also see, Euclid GCD Algorithm

FAQs

What is a subsequence in a string?
A subsequence in a string is a new string formed from the original string by removing some (or none) of the characters without affecting the relative ordering of the remaining characters. (For example, "abb" is a subsequence of "aabbcc," but "acb" is not.)
What is a prime string?
Prime string is a string that is a prime number when converted into its numeric form. A prime number is a number that is divisible only by 1 and the number itself. For example, 2, 3, 5, 7, 11, 13 are all prime numbers.