Максимальное преобразование веса данной строки


Сложный уровень средний
Часто спрашивают в Амазонка BlackRock ByteDance CodeNation Де Шоу Expedia JP Morgan Ола Кабс
Динамическое программирование строка

Постановка задачи

Преобразование максимального веса данной строковой задачи утверждает, что данная строка состоит только из двух символов «A» и «B». У нас есть операция, в которой мы можем преобразовать строку в другую, переключая любой символ. Таким образом, возможно множество преобразований. Из всех возможных преобразований найдите вес максимального преобразования веса.

Алгоритм

Weight of string = weight of total pairs + weight of single characters - total number of toggles.
Two different consecutive characters are considered as pairs.
Weight of single pair (both characters are different) = 2
Weight of single character = 1
(These values are just some random values and can be taken as input)

ПримерМаксимальное преобразование веса данной строки

BA
2

Объяснение:

Есть четыре возможности для преобразования строки «AA»:

AB → 2 - 1 = 1

БА → 2 - 1 = 1

AA → 2

BB → 2

Поскольку все эти преобразования имеют одинаковый вес, мы можем выбрать одно из любых возможных преобразований.

BAA
3

Объяснение: Всего существует 8 преобразований, из которых преобразования, содержащие одну пару и один единственный символ, имеют максимальное значение.

 

Подход для максимального преобразования веса данной строки

Наивный подход

Мы делаем все возможные преобразования, переключая каждого персонажа. После выполнения всех преобразований мы находим значение каждого преобразования, а затем находим максимальное значение, вычисляя значение каждого преобразования.

Эффективный подход

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

Поскольку исходную (или исходную) задачу можно преобразовать в более мелкие подзадачи, мы будем использовать динамическое программирование для хранения подзадач и их дальнейшего использования.

Код:

Код C ++ для преобразования максимального веса заданной строковой задачи

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

int pairCost, toggleCost;

int maxWeightOfTransformation(string s, vector<int> &dp, int i, int stringLength){
    //base case
    if(i>=stringLength)
        return 0;
    if(dp[i]!=-1)
        return dp[i];

    // consider current character as a single character(not a pair)
    int answer = 1 + maxWeightOfTransformation(s, dp, i+1, stringLength);
    if(i+1<stringLength){
        if(s[i]!=s[i+1])
            answer = max(pairCost + maxWeightOfTransformation(s, dp, i+2, stringLength), answer);
        else
            answer = max(pairCost-toggleCost + maxWeightOfTransformation(s, dp, i+2, stringLength), answer);
    }
    return dp[i] = answer;
}

int main()
{
    string s;cin>>s;
    cout<<"Enter pairCost and toggleCost"<<endl;
    cin>>pairCost>>toggleCost;
    int stringLength = s.size();
    vector<int> dp(stringLength, -1);
    cout << "Maximum weight of a transformation of "<<s<<" is " <<maxWeightOfTransformation(s, dp, 0, stringLength);
    return 0;
}
AB
Enter pairCost and toggleCost
2 1
Maximum weight of a transformation of AB is 2

Код Java для преобразования максимального веса заданной строки

import java.util.*;

class Main{
    static int pairCost, toggleCost;
    
    static int maxWeightOfTransformation(String s, int[] dp, int i, int stringLength){
        //base case
        if(i>=stringLength)
            return 0;
        if(dp[i]!=-1)
            return dp[i];
    
        // consider current character as a single character(not a pair)
        int answer = 1 + maxWeightOfTransformation(s, dp, i+1, stringLength);
        if(i+1<stringLength){
            if(s.charAt(i)!=s.charAt(i+1))
                answer = Math.max(pairCost + maxWeightOfTransformation(s, dp, i+2, stringLength), answer);
            else
                answer = Math.max(pairCost-toggleCost + maxWeightOfTransformation(s, dp, i+2, stringLength), answer);
        }
        return dp[i] = answer;
    }
    
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        System.out.println("Enter pairCost and toggleCost");
        pairCost=sc.nextInt();
        toggleCost=sc.nextInt();
        int stringLength = s.length();
        int dp[] = new int[stringLength];
        for(int i = 0;i<stringLength;i++)dp[i]=-1;
        int answer = maxWeightOfTransformation(s, dp, 0, stringLength);
        System.out.println("Maximum weight of a transformation of "+s+" is "+answer);
    }
}
AB 
Enter pairCost and toggleCost 
2 1
Maximum weight of a transformation of AB is 2

Анализ сложности

Сложность времени: НА)

Поскольку мы использовали алгоритм, который использует одномерный DP, и переход между состояниями также O (1). Это заставляет алгоритм работать с общей временной сложностью O (N).

Космическая сложность: НА)

Здесь мы использовали одномерный массив для DP, поэтому алгоритм имеет пространственную сложность O (N).