Check if a given string is made up of two alternating characters
Given a string str, the task is to check whether the given string is made up of only two alternating characters.
Examples:
Input: str = “ABABABAB”
Output: Yes
Input: str = “XYZ”
Output: No
Approach: In order for the string to be made up of only two alternating characters, it must satisfy the following conditions:
- All the characters at odd indices must be same.
- All the characters at even indices must be same.
- str[0] != str[1] (This is because string of type “AAAAA” where a single character is repeated a number of time will also satisfy the above two conditions)
Below is the implementation of the above approach:
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function that returns true if the string
// is made up of two alternating characters
bool isTwoAlter(string s)
{
// Check if ith character matches
// with the character at index (i + 2)
for (int i = 0; i < s.length() - 2; i++) {
if (s[i] != s[i + 2]) {
return false;
}
}
// If string consists of a single
// character repeating itself
if (s[0] == s[1])
return false;
return true;
}
// Driver code
int main()
{
string str = "ABAB";
if (isTwoAlter(str))
cout << "Yes";
else
cout << "No";
return 0;
}
// Java implementation of the approach
import java.io.*;
class GFG
{
// Function that returns true if the string
// is made up of two alternating characters
static boolean isTwoAlter(String s)
{
// Check if ith character matches
// with the character at index (i + 2)
for (int i = 0; i < s.length() - 2; i++)
{
if (s.charAt(i) != s.charAt(i + 2))
{
return false;
}
}
// If string consists of a single
// character repeating itself
if (s.charAt(0) == s.charAt(1))
return false;
return true;
}
// Driver code
public static void main (String[] args)
{
String str = "ABAB";
if (isTwoAlter(str))
System.out.print( "Yes");
else
System.out.print("No");
}
}
// This code is contributed by anuj_67..
# Function that returns true if the string
# is made up of two alternating characters
def isTwoAlter( s):
# Check if ith character matches
# with the character at index (i + 2)
for i in range ( len( s) - 2) :
if (s[i] != s[i + 2]) :
return False
#If string consists of a single
#character repeating itself
if (s[0] == s[1]):
return False
return True
# Driver code
if __name__ == "__main__":
str = "ABAB"
if (isTwoAlter(str)):
print ( "Yes")
else:
print ("No")
# This code is contributed by ChitraNayal
// C# implementation of the approach
using System;
class GFG
{
// Function that returns true if the string
// is made up of two alternating characters
static bool isTwoAlter(string s)
{
// Check if ith character matches
// with the character at index (i + 2)
for (int i = 0; i < s.Length - 2; i++)
{
if (s[i] != s[i +2])
{
return false;
}
}
// If string consists of a single
// character repeating itself
if (s[0] == s[1])
return false;
return true;
}
// Driver code
public static void Main()
{
string str = "ABAB";
if (isTwoAlter(str))
Console.WriteLine( "Yes");
else
Console.WriteLine("No");
}
}
// This code is contributed by AnkitRai01
// Function that returns true if the string
// is made up of two alternating characters
function isTwoAlter(s) {
// Check if ith character matches
// with the character at index (i + 2)
for (let i = 0; i < s.length - 2; i++) {
if (s[i] != s[i + 2]) {
return false;
}
}
// If string consists of a single
// character repeating itself
if (s[0] == s[1]) {
return false;
}
return true;
}
// Driver code
let str = "ABAB";
if (isTwoAlter(str)) {
console.log("Yes");
} else {
console.log("No");
}
Output
Yes
Time Complexity : O(N)
Auxiliary Space : O(1)
Using two characters to check alternating pattern:
Approach:
Check if the length of the given string is 1, then return False.
Assign the first character of the string to a variable called “first_char”.
Initialize an empty string variable called “second_char”.
Iterate over the string starting from the second character.
If the current character is not equal to the first character, check if “second_char” is empty, if it is, assign the current character to “second_char”, else if the current character is not equal to “second_char”, return False.
If the loop completes without returning False, return True.
#include <iostream>
#include <string>
#include <chrono>
using namespace std;
bool is_alternating_string(string str) {
if (str.length() == 1) {
return false;
}
char first_char = str[0];
char second_char = '\0'; // Using '\0' to represent an uninitialized character
for (size_t i = 1; i < str.length(); i++) {
if (str[i] != first_char) {
if (second_char == '\0') {
second_char = str[i];
} else if (str[i] != second_char) {
return false;
}
}
}
return true;
}
int main() {
string input_str1 = "ABABABAB";
string input_str2 = "XYZ";
auto start_time = chrono::high_resolution_clock::now();
bool result1 = is_alternating_string(input_str1);
bool result2 = is_alternating_string(input_str2);
auto end_time = chrono::high_resolution_clock::now();
cout << "Input: str = " << input_str1 << ", Output: " << (result1 ? "Yes" : "No") << endl;
cout << "Input: str = " << input_str2 << ", Output: " << (result2 ? "Yes" : "No") << endl;
// Calculate and print the time taken in seconds
auto duration = chrono::duration_cast<chrono::microseconds>(end_time - start_time);
double time_taken = duration.count() / 1000000.0;
cout << "Time taken: " << time_taken << " seconds" << endl;
return 0;
}
/*package whatever //do not write package name here */
import java.io.*;
public class GFG {
public static boolean isAlternatingString(String str) {
if (str.length() == 1) {
return false;
}
char firstChar = str.charAt(0);
char secondChar = '\0'; // Using '\0' to represent an uninitialized character
for (int i = 1; i < str.length(); i++) {
if (str.charAt(i) != firstChar) {
if (secondChar == '\0') {
secondChar = str.charAt(i);
} else if (str.charAt(i) != secondChar) {
return false;
}
}
}
return true;
}
public static void main(String[] args) {
String inputStr1 = "ABABABAB";
String inputStr2 = "XYZ";
long startTime = System.nanoTime();
boolean result1 = isAlternatingString(inputStr1);
boolean result2 = isAlternatingString(inputStr2);
long endTime = System.nanoTime();
System.out.println("Input: str = "+inputStr1+" Output: " + (result1 ? "Yes" : "No"));
System.out.println("Input: str = "+inputStr2+" Output: " + (result2 ? "Yes" : "No"));
// Calculate and print the time taken in seconds
long duration = endTime - startTime;
double timeTaken = duration / 1000000.0;
System.out.println("Time taken: " + timeTaken + " seconds");
}
}
//This code is contributed by Rohit Singh
import time
def is_alternating_string(str):
if len(str) == 1:
return False
first_char = str[0]
second_char = ""
for i in range(1, len(str)):
if str[i] != first_char:
if second_char == "":
second_char = str[i]
elif str[i] != second_char:
return False
return True
# Testing the function
input_str1 = "ABABABAB"
input_str2 = "XYZ"
start_time = time.time()
result1 = is_alternating_string(input_str1)
result2 = is_alternating_string(input_str2)
end_time = time.time()
print("Approach 1:")
print("Input: str = ", input_str1, ", Output: ", "Yes" if result1 else "No")
print("Input: str = ", input_str2, ", Output: ", "Yes" if result2 else "No")
print("Time taken: ", end_time - start_time, " seconds")
using System;
using System.Diagnostics;
class Program
{
static bool IsAlternatingString(string str)
{
if (str.Length == 1)
{
return false;
}
char firstChar = str[0];
char secondChar = '\0'; // Using '\0' to represent an uninitialized character
for (int i = 1; i < str.Length; i++)
{
if (str[i] != firstChar)
{
if (secondChar == '\0')
{
secondChar = str[i];
}
else if (str[i] != secondChar)
{
return false;
}
}
}
return true;
}
static void Main(string[] args)
{
string inputStr1 = "ABABABAB";
string inputStr2 = "XYZ";
Stopwatch stopwatch = new Stopwatch();
stopwatch.Start();
bool result1 = IsAlternatingString(inputStr1);
bool result2 = IsAlternatingString(inputStr2);
stopwatch.Stop();
Console.WriteLine("Input: str = " + inputStr1 +
", Output: " + (result1 ? "Yes" : "No"));
Console.WriteLine("Input: str = " + inputStr2 +
", Output: " + (result2 ? "Yes" : "No"));
// Calculate and print the time taken in seconds
double timeTaken = stopwatch.Elapsed.TotalSeconds;
Console.WriteLine("Time taken: " + timeTaken + " seconds");
}
}
function isAlternatingString(str) {
if (str.length === 1) {
return false;
}
let firstChar = str[0];
let secondChar = "";
for (let i = 1; i < str.length; i++) {
if (str[i] !== firstChar) {
if (secondChar === "") {
secondChar = str[i];
} else if (str[i] !== secondChar) {
return false;
}
}
}
return true;
}
// Testing the function
let inputStr1 = "ABABABAB";
let inputStr2 = "XYZ";
let startTime = Date.now();
let result1 = isAlternatingString(inputStr1);
let result2 = isAlternatingString(inputStr2);
let endTime = Date.now();
console.log("Approach 1:");
console.log("Input: str =", inputStr1, ", Output:", result1 ? "Yes" : "No");
console.log("Input: str =", inputStr2, ", Output:", result2 ? "Yes" : "No");
console.log("Time taken:", (endTime - startTime) / 1000, "seconds");
Output
Input: str = ABABABAB, Output: Yes Input: str = XYZ, Output: No Time taken: 4e-06 seconds
Time Complexity: O(n)
Auxiliary Space: O(1)
Approach :
We can solve this problem using set approach.
Follow the below steps :
- Firsly, convert the string into a set to get unique characters
- If the size of the set is not 2, return No.
- Otherwise, create alternating sequences using the two characters & check if they match the given string
- Return Yes if they match, otherwise return No.
Below is the implementation of the above approach:
#include <iostream>
#include <unordered_set>
#include <string>
using namespace std;
string is_alternating_string(string str) {
unordered_set<char> unique_chars;
// Convert the string into a set to get unique characters
for (char ch : str) {
unique_chars.insert(ch);
}
// If the size of the set is not 2, return "No"
if (unique_chars.size() != 2) {
return "No";
}
// Get the two characters from the set
char char1 = *unique_chars.begin();
char char2 = *(++unique_chars.begin());
// Create alternating sequences using the two characters
string alternating_seq = string(1, char1) + string(1, char2);
// Check if the alternating sequences match the given string
for (int i = 0; i < str.length(); i += 2) {
if (str.substr(i, 2) != alternating_seq && str.substr(i, 2) != string(1, char2) + string(1, char1)) {
return "No";
}
}
// If all sequences match, return "Yes"
return "Yes";
}
int main() {
// Driver code
cout << is_alternating_string("ABABABAB") << endl;
return 0;
}
import java.util.HashSet;
public class Main {
public static String isAlternatingString(String str) {
HashSet<Character> uniqueChars = new HashSet<>();
// Convert the string into a set to get unique characters
for (char ch : str.toCharArray()) {
uniqueChars.add(ch);
}
// If the size of the set is not 2, return "No"
if (uniqueChars.size() != 2) {
return "No";
}
// Get the two characters from the set
char char1 = str.charAt(0);
char char2 = 0;
for (char ch : str.toCharArray()) {
if (ch != char1) {
char2 = ch;
break;
}
}
// Create alternating sequences using the two characters
String alternatingSeq = String.valueOf(char1) + char2;
// Check if the alternating sequences match the given string
for (int i = 0; i < str.length(); i += 2) {
if (!str.substring(i, i + 2).equals(alternatingSeq) && !str.substring(i, i + 2).equals(String.valueOf(char2) + char1)) {
return "No";
}
}
// If all sequences match, return "Yes"
return "Yes";
}
// Driver code
public static void main(String[] args) {
// Example usage
System.out.println(isAlternatingString("ABABABAB"));
}
}
def is_alternating_string(str):
# Convert the string into a set to get unique characters
unique_chars = set(str)
# If the size of the set is not 2, return "No"
if len(unique_chars) != 2:
return "No"
# Get the two characters from the set
char1, char2 = unique_chars
# Create alternating sequences using the two characters
alternating_seq = char1 + char2
# Check if the alternating sequences match the given string
for i in range(0, len(str), 2):
if str[i:i+2] != alternating_seq and str[i:i+2] != alternating_seq[::-1]:
return "No"
# If all sequences match, return "Yes"
return "Yes"
# Test cases
print(is_alternating_string("ABABABAB"))
function isAlternatingString(str) {
// Convert the string into a set to get unique characters
let uniqueChars = new Set(str);
// If the size of the set is not 2, return "No"
if (uniqueChars.size !== 2) {
return "No";
}
// Get the two characters from the set
let char1, char2;
for (let char of uniqueChars) {
char1 = char1 || char;
char2 = char !== char1 ? char : char2;
}
// Create alternating sequences using the two characters
let alternatingSeq = char1 + char2;
// Check if the alternating sequences match the given string
for (let i = 0; i < str.length; i += 2) {
if (str.slice(i, i + 2) !== alternatingSeq && str.slice(i, i + 2) !== alternatingSeq.split('').reverse().join('')) {
return "No";
}
}
// If all sequences match, return "Yes"
return "Yes";
}
// Test cases
console.log(isAlternatingString("ABABABAB"));
Output
Yes
Time complexity: O(n), where n is the length of the string.
Auxiliary Space: O(1)
Contact Us