特定の文字列の最大重み変換


難易度 ミディアム
よく聞かれる Amazon (アマゾン) ブラックロック ByteDance コードネーション DEショウ エクスペディア JPモルガン オラキャブ
動的計画法 文字列

問題文

与えられた文字列問題の最大重み変換は、XNUMXつの文字「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」にはXNUMXつの可能性があり、次のように変換されます。

AB→2– 1 = 1

BA→2– 1 = 1

AA→2

BB→2

これらの変換はすべて同じ重みであるため、可能な変換のXNUMXつを選択できます。

BAA
3

説明:合計8つの変換があり、そのうちXNUMXつのペアとXNUMXつの単一文字を持つ変換の最大値があります。

 

与えられた文字列の最大の重み変換のためのアプローチ

素朴なアプローチ

各キャラクターを切り替えることで、可能なすべての変換を行います。 すべての変換を行った後、各変換の値を見つけ、次に各変換の値を計算して最大値を見つけます。

効率的なアプローチ

再帰を使用して、プルーニングを使用して計算を減らすことにより、特定の文字列の最大の重み変換を見つけます。 現在の文字とXNUMX番目の文字が異なる場合、これはペアです。 この場合、最初の文字を変更して先に進むか、文字を切り替えずに先に進むかのXNUMXつのオプションがあります。 もうXNUMXつの条件は、現在の文字とXNUMX番目の文字が同じである場合です。 この場合、キャラクターを切り替えてペアにするか、切り替えずに先に進みます。

最初の(または元の)問題はより小さなサブ問題に変換できるため、 動的計画法 サブ問題を保存し、さらに使用します。

コード

与えられた文字列問題の最大の重み変換のための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

複雑さの分析

時間の複雑さ: オン)

1D DPを使用するアルゴリズムを使用しているため、状態間の遷移もO(1)です。 これにより、アルゴリズムはO(N)の合計時間計算量で実行されます。

スペースの複雑さ: オン)

ここでは、DPに1D配列を使用しているため、アルゴリズムにはO(N)空間の複雑さがあります。