Битоническая строка

Опубликовано: 1 Января, 2022

Для данной строки str задача состоит в том, чтобы проверить, является ли эта строка Bitonic String или нет. Если строка str - это Bitonic String, то выведите «YES», иначе выведите «NO» .

A Bitonic String is a string in which the characters are arranged in increasing order followed by decreasing order of their ASCII values. 
 

Примеры:

Input: str = “abcdfgcba” 
Output: YES 
Explanation: 
In the above string, the ASCII values first increases {a, b, c, d, f, g} and then decreases {g, c, b, a}.
Input: str = “abcdwef” 
Output: NO 
 

Подход:
Чтобы решить эту проблему, нам просто нужно пройти по строке и проверить, соответствуют ли значения ASCII символов строки какому-либо из следующих шаблонов:

  • Строго возрастает.
  • Строго убывает.
  • Строго возрастающий, за которым следует строгое уменьшение.

Выполните следующие действия, чтобы решить проблему:

  1. Начните обход строки и продолжайте проверять, больше ли значение ASCII следующего символа, чем значение ASCII текущего символа.
  2. Если в какой-то момент значение ASCII следующего символа не превышает значение ASCII текущего символа, прервите цикл.
  3. Снова начните переход с указанного выше индекса разрыва и проверьте, меньше ли значение ASCII следующего символа, чем значение ASCII текущего символа.
  4. Если в любой момент значение ASCII следующего символа не меньше, чем значение ASCII текущего символа до достижения конца массива, выведите «NO» и прервите цикл.
  5. Если конец массива достигнут успешно, выведите «YES» .

Ниже представлена реализация описанного выше подхода:

C ++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to check if the given
// string is bitonic
int checkBitonic(string s)
{
int i, j;
// Check for increasing sequence
for (i = 1; i < s.size(); i++) {
if (s[i] > s[i - 1])
continue ;
if (s[i] <= s[i - 1])
break ;
}
// If end of string has been reached
if (i == s.size() - 1)
return 1;
// Check for decreasing sequence
for (j = i + 1; j < s.size();
j++) {
if (s[j] < s[j - 1])
continue ;
if (s[j] >= s[j - 1])
break ;
}
i = j;
// If the end of string hasn't
// been reached
if (i != s.size())
return 0;
// Return true if bitonic
return 1;
}
// Driver Code
int main()
{
// Given string
string s = "abcdfgcba" ;
// Function Call
(checkBitonic(s) == 1)
? cout << "YES"
: cout << "NO" ;
return 0;
}

Джава

// Java program for the above approach
import java.util.*;
class GFG{
// Function to check if the given
// String is bitonic
static int checkBitonic( char []s)
{
int i, j;
// Check for increasing sequence
for (i = 1 ; i < s.length; i++)
{
if (s[i] > s[i - 1 ])
continue ;
if (s[i] <= s[i - 1 ])
break ;
}
// If end of String has been reached
if (i == s.length - 1 )
return 1 ;
// Check for decreasing sequence
for (j = i + 1 ; j < s.length; j++)
{
if (s[j] < s[j - 1 ])
continue ;
if (s[j] >= s[j - 1 ])
break ;
}
i = j;
// If the end of String hasn't
// been reached
if (i != s.length)
return 0 ;
// Return true if bitonic
return 1 ;
}
// Driver Code
public static void main(String[] args)
{
// Given String
String s = "abcdfgcba" ;
// Function Call
System.out.print((checkBitonic(
s.toCharArray()) == 1 ) ? "YES" : "NO" );
}
}
// This code is contributed by PrinciRaj1992

Python3

# Python3 program for the above approach
# Function to check if the given
# string is bitonic
def checkBitonic(s):
i = 0
j = 0
# Check for increasing sequence
for i in range ( 1 , len (s)):
if (s[i] > s[i - 1 ]):
continue ;
if (s[i] < = s[i - 1 ]):
break ;
# If end of string has been reached
if (i = = ( len (s) - 1 )):
return True ;
# Check for decreasing sequence
for j in range (i + 1 , len (s)):
if (s[j] < s[j - 1 ]):
continue ;
if (s[j] > = s[j - 1 ]):
break ;
i = j;
# If the end of string hasn't
# been reached
if (i ! = len (s) - 1 ):
return False ;
# Return true if bitonic
return True ;
# Driver code
# Given string
s = "abcdfgcba"
# Function Call
if (checkBitonic(s)):
print ( "YES" )
else :
print ( "NO" )
# This code is contributed by grand_master

C #

// C# program for the above approach
using System;
class GFG{
// Function to check if the given
// String is bitonic
static int checkBitonic( char []s)
{
int i, j;
// Check for increasing sequence
for (i = 1; i < s.Length; i++)
{
if (s[i] > s[i - 1])
continue ;
if (s[i] <= s[i - 1])
break ;
}
// If end of String has been reached
if (i == s.Length - 1)
return 1;
// Check for decreasing sequence
for (j = i + 1; j < s.Length; j++)
{
if (s[j] < s[j - 1])
continue ;
if (s[j] >= s[j - 1])
break ;
}
i = j;
// If the end of String hasn't
// been reached
if (i != s.Length)
return 0;
// Return true if bitonic
return 1;
}
// Driver Code
public static void Main(String[] args)
{
// Given String
String s = "abcdfgcba" ;
// Function call
Console.Write((checkBitonic(
s.ToCharArray()) == 1) ? "YES" : "NO" );
}
}
// This code is contributed by PrinciRaj1992

Javascript

<script>
// Javascript program for the above approach
// Function to check if the given
// string is bitonic
function checkBitonic(s)
{
var i, j;
// Check for increasing sequence
for (i = 1; i < s.length; i++) {
if (s[i] > s[i - 1])
continue ;
if (s[i] <= s[i - 1])
break ;
}
// If end of string has been reached
if (i == s.length - 1)
return 1;
// Check for decreasing sequence
for (j = i + 1; j < s.length;
j++) {
if (s[j] < s[j - 1])
continue ;
if (s[j] >= s[j - 1])
break ;
}
i = j;
// If the end of string hasn't
// been reached
if (i != s.length)
return 0;
// Return true if bitonic
return 1;
}
// Driver Code
// Given string
var s = "abcdfgcba" ;
// Function Call
(checkBitonic(s) == 1)
? document.write( "YES" )
: document.write( "NO" );
// This code is contributed by itsok.
</script>
Выход:
 ДА

Сложность времени: O (N)
Вспомогательное пространство: O (1)

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по доступной для студентов цене и будьте готовы к работе в отрасли. Получите все важные математические концепции для соревновательного программирования с курсом Essential Maths for CP по доступной для студентов цене.

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.