Заменять '?' в строке, в которой нет двух одинаковых соседних символов

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

Дана строка S длины N, состоящая из «?» и строчные буквы, задача заменить «?» строчными буквами, так что никакие соседние символы не совпадают. Если существует более одной возможной комбинации, выведите любую из них.

Примеры:

Input: S = “?a?a”
Output: baba
Explanation:
Replacing all ‘?’s with ‘b’ modifies the string to “baba”.
Since no adjacent characters in “baba” are the same, print the string as the answer.

Input: S = “???”
Output: aca
Explanation:
Replace first ‘?’ with ‘a’.
Replace second ‘?’ with ‘c’.
Replace third ‘?’ with ‘a’. Now, the modified string is “aca”.
Therefore, there are no adjacent characters in “ca” which are same.

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Наивный подход: самый простой подход - попытаться сгенерировать все возможные перестановки данной строки, состоящей из строчных букв. Всего может быть 26 N струн. В каждой из этих строк проверьте, совпадают ли соседние символы или нет, и все ли строчные символы в данной строке соответствуют выбранной перестановке строки.

Сложность времени: O (N * 26 N ), где N - длина данной строки.
Вспомогательное пространство: O (N)

Эффективный подход: для оптимизации описанного выше подхода идея состоит в том, чтобы заменить все символы "?" символом 'a' и проверьте, равен ли этот символ соседнему символу или нет. Если он равен соседнему символу, увеличьте текущий символ на единицу. Ниже приведены шаги:

  1. Если первый символ строки - '?' затем замените его на 'a' и, если он равен следующему символу, увеличьте текущий символ на 1
  2. Пройдите по заданной строке, используя переменную i в диапазоне [1, N - 1], и если текущий символ - '?' и сделайте следующее:
    • Обновить символ в индексе i как s [i] = 'a' .
    • Теперь, если символы с индексом i и (i - 1) совпадают, увеличьте текущий символ на 1 .
    • Теперь, если символы с индексом i и (i + 1) совпадают, увеличьте текущий символ на 1 .
    • Теперь, если символы с индексом i и (i - 1) снова совпадают, увеличьте текущий символ на 1 . Этот шаг является обязательным, потому что после символа приращения на предыдущем шаге возможно, что символы с индексом i и (i - 1) совпадают.
  3. Если последний символ строки - '?' затем замените его на 'a' и, если он равен предыдущему символу, увеличьте последний символ на 1
  4. Распечатайте строку после вышеуказанных шагов.

Below is the implementation of the above approach:

C++

// C++ program for the above approach
 
#include "bits/stdc++.h"
using namespace std;
 
// Function that replace all "?" with
// lowercase alphabets such that each
// adjacent character is different
string changeString(string S)
{
    // Store the given string
    string s = S;
 
    int N = (int)s.length();
 
    // If the first character is "?"
    if (s[0] == "?") {
        s[0] = "a";
        if (s[0] == s[1]) {
            s[0]++;
        }
    }
 
    // Traverse the string [1, N - 1]
    for (int i = 1; i < N - 1; i++) {
 
        // If the current character is "?"
        if (s[i] == "?") {
 
            // Change the character
            s[i] = "a";
 
            // Check equality with
            // the previous character
            if (s[i] == s[i - 1]) {
                s[i]++;
            }
 
            // Check equality with
            // the next character
            if (s[i] == s[i + 1]) {
                s[i]++;
            }
 
            // Check equality with
            // the previous character
            if (s[i] == s[i - 1]) {
                s[i]++;
            }
        }
    }
 
    // If the last character is "?"
    if (s[N - 1] == "?") {
 
        // Change character
        s[N - 1] = "a";
 
        // Check with previous character
        if (s[N - 1] == s[N - 2]) {
            s[N - 1]++;
        }
    }
 
    // Return the resultant string
    return s;
}
 
// Driver Code
int main()
{
    // Given string S
    string S = "?a?a";
 
    // Function Call
    cout << changeString(S);
 
    return 0;
}

Java

// Java program for
// the above approach
class GFG{
 
// Function that replace all "?" with
// lowercase alphabets such that each
// adjacent character is different
static String changeString(String S)
{
  // Store the given String
  char []s = S.toCharArray();
 
  int N = (int)S.length();
 
  // If the first character is "?"
  if (s[0] == "?")
  {
    s[0] = "a";
    if (s[0] == s[1])
    {
      s[0]++;
    }
  }
 
  // Traverse the String [1, N - 1]
  for (int i = 1; i < N - 1; i++)
  {
    // If the current
    // character is "?"
    if (s[i] == "?")
    {
      // Change the character
      s[i] = "a";
 
      // Check equality with
      // the previous character
      if (s[i] == s[i - 1])
      {
        s[i]++;
      }
 
      // Check equality with
      // the next character
      if (s[i] == s[i + 1])
      {
        s[i]++;
      }
 
      // Check equality with
      // the previous character
      if (s[i] == s[i - 1])
      {
        s[i]++;
      }
    }
  }
 
  // If the last character is "?"
  if (s[N - 1] == "?")
  {
    // Change character
    s[N - 1] = "a";
 
    // Check with previous
    // character
    if (s[N - 1] == s[N - 2])
    {
      s[N - 1]++;
    }
  }
 
  String ans = "";
   
  for(int  i = 0; i < s.length; i++)
  {
    ans += s[i];
  }
   
  // Return the resultant String
  return ans;
}
 
// Driver Code
public static void main(String[] args)
{
  // Given String S
  String S = "?a?a";
 
  // Function Call
  System.out.print(changeString(S));
}
}
 
// This code is contributed by Rajput-Ji

Python3

# Python3 program for
# the above approach
 
# Function that replace all "?" with
# lowercase alphabets such that each
# adjacent character is different
def changeString(S):
     
    # Store the given String
    N = len(S)
    s = [" "] * (len(S))
     
    for i in range(len(S)):
        s[i] = S[i]
 
    # If the first character is "?"
    if (s[0] == "?"):
        s[0] = "a"
         
        if (s[0] == s[1]):
            s[0] = chr(ord(s[0]) + 1)
 
    # Traverse the String [1, N - 1]
    for i in range(1, N - 1):
         
        # If the current
        # character is "?"
        if (s[i] == "?"):
             
            # Change the character
            s[i] = "a"
 
            # Check equality with
            # the previous character
            if (s[i] == s[i - 1]):
                s[i] =  chr(ord(s[i]) + 1)
 
            # Check equality with
            # the next character
            if (s[i] == s[i + 1]):
                s[i] =  chr(ord(s[i]) + 1)
 
            # Check equality with
            # the previous character
            if (s[i] == s[i - 1]):
                s[i] =  chr(ord(s[i]) + 1)
 
    # If the last character is "?"
    if (s[N - 1] == "?"):
         
        # Change character
        s[N - 1] = "a"
         
        # Check with previous
        # character
        if (s[N - 1] == s[N - 2]):
            s[N - 1] += 1
 
    ans = ""
    for i in range(len(s)):
        ans += s[i]
         
    # Return the resultant String
    return ans
 
# Driver Code
if __name__ == "__main__":
     
    # Given String S
    S = "?a?a"
 
    # Function Call
    print(changeString(S))
 
# This code is contributed by gauravrajput1

C#

// C# program for the above approach
using System;
  
class GFG{
 
// Function that replace all "?" with
// lowercase alphabets such that each
// adjacent character is different
static string changeString(string S)
{
   
  // Store the given String
  char []s = S.ToCharArray();
   
  int N = S.Length;
 
  // If the first character is "?"
  if (s[0] == "?")
  {
    s[0] = "a";
    if (s[0] == s[1])
    {
      s[0]++;
    }
  }
 
  // Traverse the String [1, N - 1]
  for(int i = 1; i < N - 1; i++)
  {
     
    // If the current
    // character is "?"
    if (s[i] == "?")
    {
       
      // Change the character
      s[i] = "a";
 
      // Check equality with
      // the previous character
      if (s[i] == s[i - 1])
      {
        s[i]++;
      }
 
      // Check equality with
      // the next character
      if (s[i] == s[i + 1])
      {
        s[i]++;
      }
 
      // Check equality with
      // the previous character
      if (s[i] == s[i - 1])
      {
        s[i]++;
      }
    }
  }
 
  // If the last character is "?"
  if (s[N - 1] == "?")
  {
     
    // Change character
    s[N - 1] = "a";
 
    // Check with previous
    // character
    if (s[N - 1] == s[N - 2])
    {
      s[N - 1]++;
    }
  }
 
  string ans = "";
   
  for(int  i = 0; i < s.Length; i++)
  {
    ans += s[i];
  }
   
  // Return the resultant String
  return ans;
}
 
// Driver Code
public static void Main()
{
   
  // Given String S
  string S = "?a?a";
 
  // Function Call
  Console.WriteLine(changeString(S));
}
}
 
// This code is contributed by sanjoy_62
Output
baba

Сложность времени: O (N), где N - длина данной строки.
Вспомогательное пространство: O (N)

РЕКОМЕНДУЕМЫЕ СТАТЬИ