MAHONEY, Circuit Judge:
This appeal is taken from the denial of a petition for a writ of habeas corpus by the United States District Court for the Eastern District of New York, Mark A. Costan-tino, Judge. The question presented is whether a New York State prisoner who has served a substantial portion of an indeterminate sentence of ten to twenty years may be resentenced to a term of eight to twenty-four years upon his motion to correct the unlawful relationship (under New York law) between the maximum and minimum terms of his sentence. Under the circumstances here presented, we conclude that such an increase in the prisoner’s maximum term disturbs his legitimate expectation in the finality of his sentence, thus violating the protection against multiple punishments guaranteed by the double jeopardy clause.
[59]*59We accordingly reverse and remand with instructions to grant the writ of habeas corpus unless, within ninety days, petitioner-appellant is resentenced so that his maximum period of imprisonment does not exceed twenty years.
Background
On June 24, 1983, petitioner-appellant Traver Stewart pleaded guilty before Justice Thomas R. Sullivan of Kings County Supreme Court to one count of attempted murder in the second degree. During his plea allocution, Stewart admitted that on September 12, 1982, during the course of a robbery of an acquaintance named Janice Bryant, he had fired a shotgun at her head or neck while she lay wounded from prior bullet wounds inflicted upon her by an accomplice of Stewart. The victim somehow survived.
Attempted murder in the second degree is a class B violent felony calling for an indeterminate prison term with a maximum of twenty-five years. See N.Y. Penal Law § 70.02(l)(a), (2)(a), and 3(a) (McKinney 1987 & Supp.1991); see also id. § 70.00(l)-(3). The minimum period of imprisonment is specified by id. § 70.02(4), see id. § 70.00(3)(b), as follows:
The minimum period of imprisonment under an indeterminate sentence for a violent felony offense must be fixed by the court at one-third of the maximum term imposed and must be specified in the sentence; provided, however, that the court may impose a minimum term which is between one-third the maximum and one-half the maximum term imposed when the sentence is for a conviction of a class B armed felony offense.
Id. § 70.02(4) (emphasis added). “Armed felony” is in turn defined by N.Y.Crim. Proc.Law § 1.20(41) (McKinney 1981) in pertinent part to mean “any violent felony offense defined in section 70.02 of the penal law that includes as an element ... possession, being armed with or causing serious physical injury by means of a deadly weapon” (emphasis added).
A plea agreement, expressly recognized by Justice Sullivan prior to accepting Stewart’s plea, provided that Stewart’s sentence would be an indeterminate term the minimum range of which would be eight to sixteen years, and the maximum range of which would be ten to twenty years. Opting for the maximum sentence permitted under the plea agreement, Justice Sullivan sentenced Stewart to a term of ten to twenty years on July 25, 1983.
While serving his term, Stewart discovered that he had been illegally sentenced to a minimum term (ten years) that was one-half of his maximum term (twenty years). Such a sentence could be imposed pursuant to N.Y. Penal Law § 70.02(4) (McKinney 1987) only if Stewart had been convicted of “a class B armed felony offense” (emphasis added). However, “[t]he crime of attempted murder in the second degree is a class B violent felony offense (Penal Law § 70.02[l][a]) but it is not an armed offense (CPL 1.20[41]).” People v. Frawley, 117 A.D.2d 613, 615, 497 N.Y.S.2d 955, 957 (2d Dep’t) (per curiam), appeal denied, 67 N.Y.2d 883, 501 N.Y.S.2d 1034, 492 N.E.2d 1241 (1986).1 This is apparently the case because N.Y.Crim.Proe.Law § 1.20(41) (McKinney 1981) specifies that the requisite possession, use, or display of a deadly weapon must be “include[d] as an element” of a violent felony offense to qualify that offense as an “armed felony.” The statutory definition of attempted murder in the second degree does not include such an [60]*60element. See N.Y.Penal Law § 125.25 (McKinney 1987 & Supp.1991). Thus, even though Stewart in fact committed the violent felony of attempted murder in the second degree by firing a deadly weapon at Janice Bryant, he was not convicted of a “class B armed felony offense” within the meaning of N.Y.Penal Law § 70.02(4) (McKinney 1987).
Accordingly, in February 1986 Stewart filed a pro se motion pursuant to N.Y.Crim. Proc.Law § 440.20(1) (McKinney 1983) to set aside his sentence on the ground that the relationship between its maximum and minimum terms was unauthorized. Specifically, Stewart “requested] that the minimum term of imprisonment permissible by statute be imposed at any scheduled resen-tencing proceeding.” Justice Sullivan granted the motion and ordered that Stewart be produced for resentencing on June 25, 1986.
At the resentencing hearing, Justice Sullivan observed that: “All of us, apparently, [Stewart’s] lawyer, the District Attorney and the Court, failed to realize the fact that the minimum had to be one third not fifty percent of the maximum sentence because of the fact that this was not an armed violent felony.” Justice Sullivan also specifically recounted that Stewart entered his plea “with the understanding that the range of [his] sentence would be not less than eight, nor more than twenty years.” Nevertheless, the court resentenced Stewart to a term of eight to twenty-four years. Stewart’s appeal from this new sentence was consolidated with the direct appeal from his conviction, and both were affirmed by the Appellate Division, Second Department. See People v. Stewart, 144 A.D.2d 601, 534 N.Y.S.2d 439 (2d Dep’t 1988) (per curiam), appeal denied, 73 N.Y.2d 896, 538 N.Y.S.2d 809, 535 N.E.2d 1349 (1989).
In affirming, the Appellate Division addressed the issue presented here as follows:
Nor do we find that the sentence of 8 to 24 years’ imprisonment which was imposed after a sentence of 10 to 20 years’ imprisonment was vacated violated the terms of the plea agreement. During the change of plea proceedings the court promised to impose a minimum sentence of 8 to 16 years and a maximum sentence of 10 to 20 years. However, the promised sentences could not legally be imposed because the defendant was neither a second felony offender when sentenced nor was the crime of attempted murder in the second degree an armed felony offense (CPL 1.20[41]; see, People v. Newton, 138 A.D.2d 415, 525 N.Y.S.2d 699). If a court is unable to impose the promised sentence, the defendant must be offered the opportunity to withdraw his plea and proceed to trial (see, People v. Pascal, 103 A.D.2d 757, 477 N.Y.S.2d 229; People v. Wheeler, 91 A.D.2d 647, 456 N.Y.S.2d 832). The defendant did not avail himself of the opportunity to withdraw his plea, and, therefore, may not now complain that his plea bargain was violated. The court imposed less than the original minimum term of imprisonment. Indeed, the defendant was benefited by the reduced minimum term because he became eligible for parole at an earlier date (Penal Law § 70.40[1]). The longer maximum term was required for the sentence to be within legal parameters. (Penal Law § 70.02[3][a]; see, People v. Garcia, 121 A.D.2d 465, 466, 503 N.Y.S.2d 151, aff'd., 69 N.Y.2d 903, 516 N.Y.S.2d 194, 508 N.E.2d 929; People v. Gillette, 33 A.D.2d 587, 304 N.Y.S.2d 296; cf., People v. Miller, 65 N.Y.2d 502, 493 N.Y.S.2d 96, 482 N.E.2d 892; People v. Williams, 34 N.Y.2d 657, 355 N.Y.S.2d 578, 311 N.E.2d 650).
144 A.D.2d at 602, 534 N.Y.S.2d at 440.
Stewart thereafter petitioned pursuant to 28 U.S.C. § 2254 (1988) for a writ of habeas corpus. The district court denied the petition, stating:
What the sentencing court did in imposing a longer maximum term with a reduced minimum term does not violate constitutional principles nor does it run afoul of the mandated presumption of vindictiveness in North Carolina v. Pearce, [395 U.S. 711, 89 S.Ct. 2072, 23 L.Ed.2d 656 (1969) ]. See People v. Garcia, 121 A.D.2d 465, 503 N.Y.S.2d 151 (2d [61]*61Dep’t 1986) aff'd., 69 N.Y.2d 903, 516 N.Y.S.2d 194, 508 N.E.2d 929 (1987). A sentencing judge has the latitude to correct an illegal sentence. The specific reasons for the correction were made known to all parties. The judge acted without vindictiveness and solely in the interest of justice.
The district court subsequently issued a certificate of probable cause. This appeal followed.
Discussion
Stewart contends on appeal that his second sentence, which included an increase in his maximum term of imprisonment from twenty to twenty-four years, violated his constitutional rights (1) not to be subjected to a second, more onerous punishment, after his original sentence had been finally imposed and he had begun to serve it; (2) not to be subjected to a more severe punishment than he had been assured in return for his guilty plea; and (3) not to be punished for having exercised his legal right to challenge a defect in his original sentence. Respondents-appellees dispute these contentions, and additionally maintain that we should not reach them because (a) they are procedurally barred, and (b) Stewart did not exhaust his state remedies with respect to the first of the above constitutional claims.
We consider first these asserted threshold barriers to our consideration of Stewart’s constitutional claims.
A. Procedural Bar.
The state maintains that Stewart’s constitutional arguments are not cognizable via habeas review because the Appellate Division rejected those claims on the basis of an adequate and independent state procedural ground. See Wainwright v. Sykes, 433 U.S. 72, 86-87, 97 S.Ct. 2497, 2506-07, 53 L.Ed.2d 594 (1977). This contention is premised upon the statement by the Appellate Division, in affirming the imposition of Stewart’s second sentence, that he had to be “offered the opportunity to withdraw his plea and proceed to trial,” but “did not avail himself of the opportunity to withdraw his plea, and, therefore, may not now complain that his plea bargain was violated.” 144 A.D.2d at 602, 534 N.Y.S.2d at 440.
There are a number of problems with this position. First, as Stewart correctly contends, the minutes of his resentencing hearing do not reveal any offer to Stewart of an opportunity to withdraw his plea. Second, any resulting bar would relate only to Stewart’s claim that his plea bargain was violated, and this is only one of the three grounds that he asserts for habeas relief. Third, and most fundamentally, the purported state procedural rule invoked here would actually be a substantive rule; to wit, that it is an adequate remedy for the constitutional violations asserted by Stewart to allow him to withdraw his guilty plea, after serving a substantial portion of his sentence, and proceed to trial. As will appear, however, the asserted rule is at odds with the double jeopardy provision of the fifth amendment to the Constitution, made applicable to the states by the due process clause of the fourteenth amendment, see Benton v. Maryland, 395 U.S. 784, 794, 89 S.Ct. 2056, 2062, 23 L.Ed.2d 707 (1969).
We conclude that Stewart’s constitutional claims are not procedurally barred.
B. Exhaustion of State Remedies.
The state concedes that Stewart raised, in the course of the state proceedings, his claims that his second sentence (1) violated his plea agreement, and (2) was imposed in retaliation for his seeking relief from his initial sentence, thus violating North Carolina v. Pearce, 395 U.S. 711, 89 S.Ct. 2072, 23 L.Ed.2d 656 (1969). The state contends, however, that Stewart did not adequately present his contention that the imposition of an increased sentence, following the commencement of his service of the initial sentence, violated the constitutional bar against double jeopardy. Accordingly, the state seeks dismissal of Stewart’s petition as a “mixed” petition containing both exhausted and unexhausted claims, citing Rose v. Lundy, 455 U.S. 509, 522, 102 S.Ct. 1198, 1205, 71 L.Ed.2d [62]*62379 (1982), and Petrucelli v. Coombe, 735 F.2d 684, 687 (2d Cir.1984). We conclude, however, that the rule against consideration of mixed petitions does not preclude our consideration of Stewart’s claims.
In Daye v. Attorney General of New York, 696 F.2d 186 (2d Cir.1982) (in banc), cert. denied, 464 U.S. 1048, 104 S.Ct. 723, 79 L.Ed.2d 184 (1984), we addressed the exhaustion issue as follows:
In summary, the ways in which a state defendant may fairly present to the state courts the constitutional nature of his claim, even without citing chapter and verse of the Constitution, include (a) reliance on pertinent federal cases employing constitutional analysis, (b) reliance on state cases employing constitutional analysis in like fact situations, (c) assertion of the claim in terms so particular as to call to mind a specific right protected by the Constitution, and (d) allegation of a pattern of facts that is well within the mainstream of constitutional litigation.
Id. at 194.
Stewart’s brief on appeal to the Appellate Division satisfied the latter two criteria. That brief introduced its argument by stating:
That this resentence violates the underlying plea bargain agreement and thus mandates reversal will be more fully treated in Point Two, infra. The appellant would initially contend, however, that the court’s resentence is an impermissible enhancement of punishment that runs afoul of our constitutional and deci-sional law. The sentence must now be modified by this Court to a period of incarceration of from 6% years to 20 years to pass constitutional muster.
This passage made clear that Stewart was advancing an argument that was (1) constitutional in nature, and (2) distinct from his contention that his plea agreement had been breached. Furthermore, while the passage serves to introduce an argument that the sentence increase was presumptively vindictive, it is well settled that the double jeopardy clause provides a measure of protection against sentence enhancement. Indeed, North Carolina v. Pearce, 395 U.S. 711, 89 S.Ct. 2072, 23 L.Ed.2d 656 (1969), the case upon which Stewart’s vindictiveness argument was premised, contains a major ruling that the double jeopardy clause requires crediting punishment already exacted toward a new sentence upon reconviction for the same offense. 395 U.S. at 718-19, 89 S.Ct. at 2077-78. In this context, Stewart’s claim that enhancement of his sentence violated constitutional decisions was sufficiently particular to call double jeopardy principles to mind. Furthermore, increased punishment for an offense upon resentencing is clearly a scenario within the mainstream of double jeopardy litigation, as demonstrated by numerous cases hereinafter cited.
We note also that in affirming Stewart’s sentence, the Appellate Division relied upon People v. Garcia, 69 N.Y.2d 903, 508 N.E.2d 929, 516 N.Y.S.2d 194 (1987), in which case the Court of Appeals “rejected] defendant’s argument that the Double Jeopardy Clause prohibited the court from correcting its own sentencing error.” 69 N.Y.2d at 904, 508 N.E.2d at 930, 516 N.Y.S.2d at 195. Further, in its memorandum to the district court in response to Stewart’s habeas petition, the state expressly conceded that Stewart had raised the double jeopardy argument in state court, and accordingly made no assertion that petitioner’s double jeopardy claim had not been exhausted. Under these circumstances, we would be free to consider the merits of Stewart’s claims even if the double jeopardy contention had not been exhausted. See Granberry v. Greer, 481 U.S. 129, 134, 107 S.Ct. 1671, 1675, 95 L.Ed.2d 119 (1987); Sanders v. Sullivan, 863 F.2d 218, 221-22 (2d Cir.1988); Davis v. Lansing, 851 F.2d 72, 76 (2d Cir.1988).
We turn to the merits.
C. The Merits.
Over a century ago, the Supreme Court recognized that the protection of the double jeopardy clause extends beyond the area of multiple prosecutions to place limits upon multiple punishments:
For of what avail is the constitutional protection against more than one trial if [63]*63there can be any number of sentences pronounced on the same verdict? Why is it that, having once been tried and found guilty, he can never be tried again for that offence? Manifestly it is not the danger or jeopardy of being a second time found guilty. It is the punishment that would legally follow the second conviction which is the real danger guarded against by the Constitution.... [W]e do not doubt that the Constitution was designed as much to prevent the criminal from being twice punished for the same offence as from being twice tried for it.
Ex parte Lange, 85 U.S. (18 Wall.) 163, 173, 21 L.Ed. 872 (1873). This concept remains vital. See, e.g., United States v. Halper, 490 U.S. 435, 109 S.Ct. 1892, 1898, 1903 & n. 10, 104 L.Ed.2d 487 (1989) (post-conviction civil penalty under False Claims Act constituted unconstitutional second punishment where not rationally related to goal of making government whole).
The Court has made clear, however, that the mere pronouncement of sentence is not accorded the degree of finality accompanying a verdict of acquittal. Thus, in United States v. DiFrancesco, 449 U.S. 117, 138—39, 101 S.Ct. 426, 438-39, 66 L.Ed.2d 328 (1980), the Court held that a sentence could be increased upon the government’s statutorily authorized direct appeal even though the defendant had already commenced service of that sentence, stating: “Under such circumstances there can be no expectation of finality in the original sentence.” Id. at 139, 101 S.Ct. at 438. Consistent with this rationale, the circuits have generally concluded that the key to double jeopardy analysis of a sentence increase is whether the defendant had a legitimate expectation in the finality of his original sentence. See, e.g., United States v. Jackson, 903 F.2d 1313, 1315 (10th Cir.1990), rev’d on other grounds, 921 F.2d 985 (10th Cir.1990) (en banc); United States v. Cochran, 883 F.2d 1012, 1016 (11th Cir.1989); Gauntlett v. Kelly, 849 F.2d 213, 218 (6th Cir.1988); United States v. Fogel, 829 F.2d 77, 87 (D.C.Cir.1987); United States v. Shue, 825 F.2d 1111, 1115 (7th Cir.), cert. denied, 484 U.S. 956, 108 S.Ct. 351, 98 L.Ed.2d 376 (1987); United States v. Crawford, 769 F.2d 253, 257 (5th Cir.1985), cert. denied, 474 U.S. 1103, 106 S.Ct. 887, 88 L.Ed.2d 922 (1986); United States v. Bello, 767 F.2d 1065, 1070 (4th Cir.1985).2
Our decisions reflect this standard. In McClain v. United States, 676 F.2d 915 (2d Cir.), cert. denied, 459 U.S. 879, 103 S.Ct. 174, 74 L.Ed.2d 143 (1982), the defendant had been sentenced to a fifteen-year term for bank robbery to be followed by a man-datorily consecutive term of ten years for use of a firearm, but the firearm conviction was vacated upon collateral review. See McClain v. United States, 643 F.2d 911 (2d Cir.), cert. denied, 452 U.S. 919, 101 S.Ct. 3057, 69 L.Ed.2d 424 (1981). We vacated the entire sentence, however, and remanded for resentencing, whereupon the district court imposed a twenty-year sentence on the surviving count. On appeal, McClain urged that the revised sentence constituted double jeopardy. We nonetheless affirmed, applying “the principles set forth in DiFrancesco,” and ruling that “appellant had no legitimate expectation of receiving only a fifteen-year sentence, because of the lack of finality accorded to sentences and because he should have been aware that under section 2113(d) he could have been sentenced to twenty-five years.” 676 F.2d at 918.
More recently, in United States v. Rico, 902 F.2d 1065 (2d Cir.), cert. denied, - U.S. -, 111 S.Ct. 352, 112 L.Ed.2d 316 (1990), we rejected a double jeopardy challenge where the trial court resentenced the defendant to the three-year term specified in her valid plea agreement in order to correct a mistakenly imposed sentence of ten months. We concluded that under the circumstances presented, the defendant “had no expectation of finality in her sentence.” Id. at 1069. Significantly, in nei[64]*64ther case did the newly imposed term exceed that which the defendant could reasonably have anticipated at his initial sentencing.
Turning to Stewart’s situation, we have no doubt that the four-year increase in his maximum sentence contravened his legitimate expectation that his maximum term had been finally determined. Before Stewart entered his guilty plea, the trial court provided him with specific assurances in this regard:
THE COURT: Now, in connection with the sentence in this case, I have told your attorney ..., and the Assistant District Attorney, that at the time of sentence I am not binding myself conclusively to anything, but that the sentence I would impose on you would depend on your probation report, but it would be between eight to 16 years in State’s prison and ten to 20 years in State’s prison; do you understand that?
THE DEFENDANT: Yes.
THE COURT: .... I’m saying that I’m going to ... decide my sentence after I read the probation report within the range that I told you; you understand that?
THE DEFENDANT: Yes.
THE COURT: Has any other promise been made to you about sentence at all?
THE DEFENDANT: No.
Emphasis added.
After the court imposed a twenty-year maximum, Stewart served approximately three years in prison with this understanding. Furthermore, his maximum period of imprisonment has real impact; his entitlement to conditional release matures upon serving two-thirds of his maximum term in “good behavior,” see N.Y.Penal Law §§ 70.40(l)(b) and 70.30(4)(a) (McKinney 1987), and he would ordinarily remain under post-release parole supervision until the expiration of the maximum term. Id. § 70.40(1).
The state contends that Stewart’s original sentence was entirely void, and that Justice Sullivan was therefore free to impose any sentence complying with the applicable sentencing statutes. We disagree. The only defect in Stewart’s original sentence was the unlawful relationship between the maximum and minimum terms. This problem was as easily correctable by a reduction in the minimum term as by an increase in the maximum term. As was said in United States v. Fogel, 829 F.2d 77, 90 (D.C.Cir.1987):
The ... court ... was free to correct the defect in the original sentence but only to the extent necessary to bring the sentence into compliance with the statute _ [T]he ... court unnecessarily increased the appellant’s sentence, thus producing a violation of the double jeopardy clause....3
The state further argues that Stewart can expect no finality in a sentence that was invalidated by his own motion. We agree that a defendant’s efforts to set aside his sentence constitute a factor militating against his finality interest, but this factor alone is not dispositive. It is clear that Stewart proceeded on the premise that the legitimate means of correcting his sentencing would be a reduction of his minimum term. In his affidavit in support of his motion for resentencing, he concluded by requesting “that the minimum term of imprisonment permissible by statute be imposed at any scheduled resentencing proceeding.” Further, the following colloquy occurred at his resentencing hearing:
[65]*65THE COURT: Mr. Stuart [sic], do you wish to say anything to me before I impose sentence.
THE DEFENDANT: Yes. In reply to the District Attorney. I feel that twenty years max is conforming with the statutory [sic] of the class B felony. I feel the minimum should be one third of the minimum [sic] imposed of twenty.
Finally, in his brief on direct appeal from his conviction and sentence, Stewart maintained: “The sentence must now be modified ... to a period of incarceration of from 6% years to 20 years so as to pass constitutional muster.”
Under all the circumstances, including the plea agreement and his service of three years imprisonment under the original sentence, we conclude that Stewart had an expectation of finality with regard to his maximum term notwithstanding his efforts to reduce his minimum term. In view of our resolution of Stewart’s double jeopardy claim in his favor, we need not separately address his due process contentions that his second sentence unconstitutionally violated his plea agreement, or was unconstitutionally vindictive.
Conclusion
The judgment of the district court is reversed, and the case is remanded with instructions to grant the writ of habeas corpus unless, within ninety days, Stewart is resentenced so that his maximum period of imprisonment does not exceed twenty years.